Definition
- Sign assignment – each number receives a + or - sign; the total of all signed numbers must equal the target.
- Algebraic reduction – let P be the positive group and N the negative group; P - N = target, P + N = total, so P = (total + target) / 2.
- Counting DP – dp[s] counts the number of subsets summing to s; dp[0] = 1; for each number, sweep s downward adding dp[s - num].
- Feasibility – if (total + target) is negative or odd, no valid assignment exists.
- Complexity – O(n * P) time, O(P) space.
The National Bank of India reconciles a net position where each pending entry can be a credit or a debit, and wants to count how many credit-debit labellings produce an exact target net balance.
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 the signed total equals T. Count the number of valid sign assignments.
At the National Bank of India, pending ledger entries can each be posted as a credit (+) or debit (-), and the reconciliation team needs to count how many labellings produce a required net position.
package com.bank.reconciliation;
public class TargetSumWays {
public static void main(String[] args) {
int[] nums = {1, 1, 1, 1, 1};
int target = 3;
System.out.println("Ways: " + countWays(nums, target));
}
static int countWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (total + target < 0 || (total + target) % 2 != 0) return 0;
int P = (total + target) / 2;
int[] dp = new int[P + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = P; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[P];
}
}
Ways: 5
How does the algebraic reduction work?
Split numbers into positive group P and negative group N. We need P - N = target and P + N = total. Adding: 2P = total + target, so P = (total + target) / 2. Now count subsets summing to P.
// nums = {1,1,1,1,1}, target = 3, total = 5
// P = (5 + 3) / 2 = 4
// Count subsets summing to 4
// Choose 4 of the five 1s: C(5,4) = 5 ways
Why are the feasibility guards needed?
If total + target is odd, P would be fractional, impossible for integer sums. If total + target is negative, P would be negative, unreachable with non-negative numbers. Both cases return 0.
package com.bank.reconciliation;
public class FeasibilityDemo {
public static void main(String[] args) {
System.out.println(countWays(new int[]{1,2,3}, 7)); // 7 > 6 -> 0
System.out.println(countWays(new int[]{1,2,3}, 2)); // (6+2)=8, even -> valid
System.out.println(countWays(new int[]{1,2,3}, 1)); // (6+1)=7, odd -> 0
}
static int countWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (total + target < 0 || (total + target) % 2 != 0) return 0;
int P = (total + target) / 2;
int[] dp = new int[P + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = P; s >= num; s--) dp[s] += dp[s - num];
}
return dp[P];
}
}
0
1
0
How does the counting DP work step by step?
Start with dp[0] = 1. For each number, iterate s from P down to num, adding dp[s - num] to dp[s]. The downward sweep ensures each number is used at most once (0/1 knapsack).
package com.bank.reconciliation;
import java.util.Arrays;
public class DPTrace {
public static void main(String[] args) {
int[] nums = {2, 3, 5};
int target = 0; // total=10, P=(10+0)/2=5
int P = 5;
int[] dp = new int[P + 1];
dp[0] = 1;
System.out.println("Init: " + Arrays.toString(dp));
for (int num : nums) {
for (int s = P; s >= num; s--) dp[s] += dp[s - num];
System.out.println("After " + num + ": " + Arrays.toString(dp));
}
System.out.println("Answer: " + dp[P]);
}
}
Init: [1, 0, 0, 0, 0, 0]
After 2: [1, 0, 1, 0, 0, 0]
After 3: [1, 0, 1, 1, 0, 1]
After 5: [1, 0, 1, 1, 0, 2]
Answer: 2
How do zeros affect the count?
A zero can be assigned + or - without changing the sum. Each zero doubles the total count. The DP handles this naturally because adding dp[s - 0] to dp[s] doubles every entry.
// nums = {0, 0, 1}, target = 1, total = 1, P = 1
// Subsets summing to 1: {1} (one subset)
// But each 0 can be in or out: 2^2 = 4 multiplier
// Total ways: 1 * 4 = 4
// Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1
What is the brute-force comparison?
Brute force tries all 2^n sign assignments. For n=20, that is over 1 million combinations. The DP runs in O(n * P) which is typically much smaller.
// Brute force (exponential)
static int bruteForce(int[] nums, int target, int index, int current) {
if (index == nums.length) return current == target ? 1 : 0;
return bruteForce(nums, target, index + 1, current + nums[index])
+ bruteForce(nums, target, index + 1, current - nums[index]);
}
// O(2^n) time, O(n) stack
// DP (pseudo-polynomial)
// O(n * P) time, O(P) space
// For nums summing to 1000 and n=20: 20 * 500 = 10,000 ops vs 1,048,576
What is the complete banking implementation?
package com.bank.reconciliation;
public class LedgerAdjustmentCounter {
public static int countAdjustmentWays(int[] amounts, int requiredNet) {
int total = 0;
for (int a : amounts) total += a;
int sumTarget = total + requiredNet;
if (sumTarget < 0 || sumTarget % 2 != 0) return 0;
int subsetTarget = sumTarget / 2;
int[] dp = new int[subsetTarget + 1];
dp[0] = 1;
for (int amount : amounts) {
for (int s = subsetTarget; s >= amount; s--) {
dp[s] += dp[s - amount];
}
}
return dp[subsetTarget];
}
public static void main(String[] args) {
int[] amounts = {100, 200, 300, 400};
int requiredNet = 200;
System.out.println("Adjustment ways: " + countAdjustmentWays(amounts, requiredNet));
}
}
Adjustment ways: 2
What are common mistakes?
The most common mistake is forgetting the feasibility guards and creating a negative-sized dp array. Another is sweeping sums upward instead of downward, which uses each number multiple times (unbounded knapsack instead of 0/1).
// WRONG: upward sweep uses each number multiple times
for (int s = num; s <= P; s++) dp[s] += dp[s - num]; // unbounded!
// CORRECT: downward sweep uses each number at most once
for (int s = P; s >= num; s--) dp[s] += dp[s - num]; // 0/1 knapsack
What should a senior engineer know?
- Algebraic transformation skill. Recognizing that signs reduce to subsets is the key insight. This pattern appears in partition-equal-subset, subset-sum-count, and coin-change-count problems.
- Counting vs feasibility. dp[s] counts ways, not just feasibility. The base case dp[0] = 1 means one way to make zero (empty subset), and the recurrence accumulates counts.
- Long overflow. For large inputs, dp values can exceed int range. Use long[] if the answer could be large.
- Negative targets. The guards handle negative targets correctly because total + target could still be a valid non-negative even number.
Visual Overview
nums = [1, 1, 1, 1, 1] target = 3 total = 5 Algebra: P - N = 3 P + N = 5 ──────── 2P = 8 -> P = 4 Count subsets summing to 4: dp[0..4]: Init: [1, 0, 0, 0, 0] +num=1: [1, 1, 0, 0, 0] +num=1: [1, 2, 1, 0, 0] +num=1: [1, 3, 3, 1, 0] +num=1: [1, 4, 6, 4, 1] +num=1: [1, 5, 10,10, 5] Answer: dp[4] = 5 The 5 assignments: +1+1+1+1-1 = 3 +1+1+1-1+1 = 3 +1+1-1+1+1 = 3 +1-1+1+1+1 = 3 -1+1+1+1+1 = 3
Key Takeaway
Target Sum looks like a brute-force sign-assignment problem, but the key move is an algebraic reduction. Splitting the numbers into those signed positive (P) and those signed negative (N), we get P - N = target and P + N = total. Adding gives P = (total + target) / 2. So counting sign assignments becomes counting subsets summing to that derived value.
I guard the edge cases first: if total + target is negative or odd, P would be impossible and the answer is zero. Otherwise I run the counting DP: seed dp[0] = 1 and for each number sweep sums downward, adding dp[s - num] to dp[s] so each number is used at most once. The answer is dp[P].
The DP runs in O(n * P) time and O(P) space, far better than the brute-force O(2^n). For inputs with zeros, each zero doubles the count because it can be signed either way without affecting the sum, and the DP handles this naturally.
At the National Bank of India, the reconciliation team used this when each pending ledger entry could be posted as a credit or debit and they needed the count of labellings producing a required net position. Explaining the algebra, the guards, and the counting recurrence shows an interviewer I can simplify a hard-looking problem into a known 0/1 Knapsack pattern.
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.
---