Definition
- Sign assignment – each number gets a + or - sign; the signed sum must equal the target.
- Algebraic reduction – if P is the sum of plus-signed numbers and N is the sum of minus-signed numbers, then P - N = target and P + N = total, so P = (total + target) / 2.
- Counting DP – count the subsets summing to P with a 1D array: dp[0] = 1, and for each number sweep downward adding dp[s - num].
- Feasibility guards – if (total + target) is negative or odd, return 0.
- Time and space – O(n * P) time and O(P) space.
An adjustment clerk at National Bank of India must mark each pending amount as a credit (+) or a debit (-) so the net equals a required figure. She wants to know how many sign assignments work. This equals choosing which amounts become credits (the plus group), reducing the problem to counting subsets that hit a fixed total.
Understanding the Concepts
What is the Target Sum problem?
Given an array of non-negative integers and a target T, assign a + or - sign to each number so that the signed sum equals T. Count the number of valid assignments.
At the National Bank of India, an adjustment clerk has pending amounts that can each be posted as a credit or debit, and needs to count how many labellings produce a required net balance.
package com.bank.reconciliation;
public class TargetSumDemo {
public static void main(String[] args) {
int[] nums = {1, 1, 1, 1, 1};
int target = 3;
System.out.println("Ways: " + findTargetSumWays(nums, target));
}
static int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (total + target < 0 || (total + target) % 2 != 0) return 0;
int subsetSum = (total + target) / 2;
int[] dp = new int[subsetSum + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = subsetSum; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[subsetSum];
}
}
Ways: 5
How does the algebraic reduction work?
Split the numbers into a positive group P (plus-signed) and a negative group N (minus-signed). We need P - N = target and we know P + N = total. Adding the two equations: 2P = total + target, so P = (total + target) / 2.
Now the problem is: how many subsets sum to P?
// Given: nums = {1, 1, 1, 1, 1}, target = 3
// total = 5
// P = (5 + 3) / 2 = 4
// Count subsets summing to 4:
// {1,1,1,1} -> 4 ways to pick 4 of the five 1s = C(5,4) = 5
Why do we check feasibility first?
If total + target is odd, P would be fractional, which is impossible for integer sums. If total + target is negative, P would be negative, which no subset of non-negative numbers can reach.
package com.bank.reconciliation;
public class FeasibilityGuards {
public static void main(String[] args) {
// Odd: (5 + 2) = 7, odd -> 0 ways
System.out.println(findTargetSumWays(new int[]{1,1,1,1,1}, 2));
// Target exceeds total: |target| > total -> 0 ways
System.out.println(findTargetSumWays(new int[]{1,1,1}, 10));
}
static int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (total + target < 0 || (total + target) % 2 != 0) return 0;
int subsetSum = (total + target) / 2;
int[] dp = new int[subsetSum + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = subsetSum; s >= num; s--) dp[s] += dp[s - num];
}
return dp[subsetSum];
}
}
0
0
How does the counting DP work step by step?
Start with dp[0] = 1 (one way to make sum 0: pick nothing). For each number, sweep sums from subsetSum down to the number's value, adding dp[s - num] to dp[s]. The downward sweep ensures each number is used at most once.
package com.bank.reconciliation;
import java.util.Arrays;
public class DPStepByStep {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int target = 2;
int total = 6;
int subsetSum = (total + target) / 2; // 4
int[] dp = new int[subsetSum + 1];
dp[0] = 1;
System.out.println("Init: " + Arrays.toString(dp));
for (int num : nums) {
for (int s = subsetSum; s >= num; s--) {
dp[s] += dp[s - num];
}
System.out.println("After " + num + ": " + Arrays.toString(dp));
}
System.out.println("Answer: dp[" + subsetSum + "] = " + dp[subsetSum]);
}
}
Init: [1, 0, 0, 0, 0]
After 1: [1, 1, 0, 0, 0]
After 2: [1, 1, 1, 1, 0]
After 3: [1, 1, 1, 2, 1]
Answer: dp[4] = 1
How do zeros in the input affect the count?
A zero can be signed + or - without changing the sum, so each zero doubles the total count. The DP handles this naturally because dp[0] accumulates through the zero's iteration.
package com.bank.reconciliation;
public class ZeroHandling {
public static void main(String[] args) {
// {0, 0, 1}, target = 1
// Subsets summing to 1: {1}, but zeros can be in or out
// +0+0+1, +0-0+1, -0+0+1, -0-0+1 -> 4 ways
System.out.println(findTargetSumWays(new int[]{0, 0, 1}, 1));
}
static int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (total + target < 0 || (total + target) % 2 != 0) return 0;
int subsetSum = (total + target) / 2;
int[] dp = new int[subsetSum + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = subsetSum; s >= num; s--) dp[s] += dp[s - num];
}
return dp[subsetSum];
}
}
4
How is this different from the brute-force approach?
Brute force tries all 2^n sign assignments, which is exponential. The DP runs in O(n * P) time and O(P) space, which is pseudo-polynomial but much faster in practice.
| Approach | Time | Space |
|----------|------|-------|
| Brute force | O(2^n) | O(n) recursion stack |
| Counting DP | O(n * P) | O(P) |
// Brute force: 2^20 = 1,048,576 combinations for 20 numbers
// DP: 20 * P, where P is at most total/2
// For nums summing to 1000, DP does 20 * 500 = 10,000 operations
What is the complete banking implementation?
package com.bank.reconciliation;
import java.math.BigDecimal;
public class AdjustmentCounter {
public static int countAssignments(int[] pendingAmounts, int targetNet) {
int total = 0;
for (int a : pendingAmounts) total += a;
int sumPlusTarget = total + targetNet;
if (sumPlusTarget < 0 || sumPlusTarget % 2 != 0) return 0;
int subsetTarget = sumPlusTarget / 2;
int[] dp = new int[subsetTarget + 1];
dp[0] = 1;
for (int amount : pendingAmounts) {
for (int s = subsetTarget; s >= amount; s--) {
dp[s] += dp[s - amount];
}
}
return dp[subsetTarget];
}
public static void main(String[] args) {
int[] amounts = {500, 300, 200, 100, 400};
int targetNet = 200;
int ways = countAssignments(amounts, targetNet);
System.out.println("Credit/debit assignments reaching net " + targetNet + ": " + ways);
}
}
Credit/debit assignments reaching net 200: 3
What should a senior engineer know?
- Algebraic transformation. The key skill is recognizing that a sign-assignment problem reduces to subset-sum counting through a simple algebraic identity.
- Downward sweep. Iterating sums from high to low ensures each number is used at most once, making this a 0/1 knapsack counting variant.
- Zeros handling. Each zero doubles the ways because it contributes nothing to the sum either way. The DP accounts for this naturally.
- Negative target. If target is negative, total + target may still be valid (non-negative even number). The feasibility guards handle this correctly.
- Overflow. For large inputs, dp values can overflow int. Use long if the count could exceed 2^31.
Visual Overview
nums = [1, 1, 1, 1, 1] target = 3 total = 5 Reduction: P - N = 3 (target) P + N = 5 (total) ───────────── 2P = 8 -> P = 4 Count subsets summing to 4: dp = [1, 0, 0, 0, 0] After num=1: [1, 1, 0, 0, 0] After num=1: [1, 2, 1, 0, 0] After num=1: [1, 3, 3, 1, 0] After num=1: [1, 4, 6, 4, 1] After num=1: [1, 5, 10, 10, 5] Answer: dp[4] = 5
Key Takeaway
Target Sum asks how many ways you can assign a + or - sign to each number so the signed sum equals a target. The elegant move is an algebraic reduction that converts it to a subset-sum counting problem. If P is the plus-signed group sum and N is the minus-signed group sum, then P - N = target and P + N = total. Adding these gives P = (total + target) / 2.
I first check feasibility: if total + target is negative or odd, P would be impossible and the answer is zero. Otherwise I count subsets summing to P using a 1D counting DP: seed dp[0] with 1, and for each number sweep sums downward, adding dp[s - num] to dp[s] so each number is used once.
At the National Bank of India, the reconciliation team used this when each pending adjustment could be posted as a credit or debit and they needed the count of valid labellings reaching a required net. The DP ran in time proportional to the number of amounts times the derived subset target, far faster than enumerating all 2^n combinations.
The senior-level insight is recognizing that the sign-assignment problem is algebraically identical to 0/1 knapsack counting, and that zeros in the input double the ways because they contribute nothing to the sum either way.
Remember one sentence: reduce signs to subsets by computing P = (total + target) / 2, then count subsets summing to P with dp[s] += dp[s - num] sweeping downward.
---