Definition
- Sign assignment – each number gets a + or - sign; the signed total must equal the target T.
- Algebraic reduction – with P as the positive group and N as the negative group, P - N = T and P + N = total, so P = (total + T) / 2.
- Counting DP – count subsets summing to P using a 1D array with dp[0] = 1 and the standard 0/1 Knapsack recurrence.
- Guards – return 0 if (total + T) is odd or if |T| exceeds total.
- Complexity – O(n * P) time, O(P) space.
The National Bank of India has a set of adjustments, each of which can be applied as a credit or a debit, and wants to count how many sign assignments produce a required net effect. By algebra this becomes counting how many subsets form the positive group, which is a 0/1 Knapsack counting problem.
Understanding the Concepts
What is the Target Sum problem?
Given a set of positive numbers and a target T, assign a + or - sign to each number so the signed total equals T. Count the number of valid assignments.
At the National Bank of India, each fixed adjustment can be posted as a credit or debit, and the reconciliation team counts how many sign choices produce the required net effect on an account.
package com.bank.reconciliation;
public class TargetSumSubset {
public static void main(String[] args) {
int[] nums = {1, 1, 2, 3};
int target = 1;
System.out.println("Ways: " + countWays(nums, target));
}
static int countWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (Math.abs(target) > total) return 0;
if ((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: 3
How does the algebraic reduction work?
Let P be the sum of plus-signed numbers and N the sum of minus-signed numbers. We need P - N = T and P + N = total (S). Adding: 2P = S + T, so P = (S + T) / 2. Counting sign assignments that reach T is counting subsets summing to P.
// nums = {1, 1, 2, 3}, target = 1, total = 7
// P = (7 + 1) / 2 = 4
// Count subsets summing to 4:
// {1, 3}, {1, 3}, {1, 1, 2} -> 3 ways
Why are two guards needed?
Guard 1: If (total + target) is odd, P is fractional, which is impossible for a sum of integers. Guard 2: If |target| exceeds total, no combination of signs can reach it.
package com.bank.reconciliation;
public class GuardsDemo {
public static void main(String[] args) {
// Odd: (7 + 2) = 9, odd -> 0
System.out.println(countWays(new int[]{1, 1, 2, 3}, 2));
// |target| > total: |10| > 7 -> 0
System.out.println(countWays(new int[]{1, 1, 2, 3}, 10));
// Negative target: (-7 + 7 = 0) / 2 = 0 -> count subsets summing to 0
System.out.println(countWays(new int[]{1, 1, 2, 3}, -7));
}
static int countWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (Math.abs(target) > total) return 0;
if ((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
0
1
How does the counting DP work step by step?
Seed dp[0] = 1 (one way to make sum 0: choose nothing). For each number, sweep sums from P down to the number, adding dp[s - num]. 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, 1, 2, 3};
int P = 4; // (7+1)/2
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]
After 1: [1, 1, 0, 0, 0]
After 1: [1, 2, 1, 0, 0]
After 2: [1, 2, 2, 2, 1]
After 3: [1, 2, 2, 3, 3]
Answer: 3
How does this compare to brute force?
Brute force enumerates all 2^n combinations. For n=20, that is over 1 million. The DP runs in O(n * P), typically much smaller.
| Approach | Time | Space |
|----------|------|-------|
| Brute force | O(2^n) | O(n) stack |
| Counting DP | O(n * P) | O(P) |
// Brute force
static int brute(int[] nums, int target, int i, int sum) {
if (i == nums.length) return sum == target ? 1 : 0;
return brute(nums, target, i+1, sum+nums[i])
+ brute(nums, target, i+1, sum-nums[i]);
}
How does this handle zeros?
For strictly positive inputs, the reduction is clean. With zeros, each zero can be signed either way without affecting the sum, which doubles the count per zero. The DP handles this naturally.
// nums = {0, 1, 1}, target = 0, total = 2, P = 1
// Subsets summing to 1: {1} (either of the two 1s) -> 2 subsets
// Each zero doubles: 2 * 2^1 = 4 ways
// Verify: +0+1-1, +0-1+1, -0+1-1, -0-1+1 -> 4 ways
What is the complete banking implementation?
package com.bank.reconciliation;
public class AdjustmentSignCounter {
public static int countSignAssignments(int[] adjustments, int requiredNet) {
int total = 0;
for (int a : adjustments) total += a;
if (Math.abs(requiredNet) > total) return 0;
int sumTarget = total + requiredNet;
if (sumTarget % 2 != 0) return 0;
int subsetTarget = sumTarget / 2;
int[] dp = new int[subsetTarget + 1];
dp[0] = 1;
for (int adj : adjustments) {
for (int s = subsetTarget; s >= adj; s--) {
dp[s] += dp[s - adj];
}
}
return dp[subsetTarget];
}
public static void main(String[] args) {
int[] adjustments = {500, 300, 200, 100};
int requiredNet = 100;
System.out.println("Sign assignments: " + countSignAssignments(adjustments, requiredNet));
}
}
Sign assignments: 2
What are common mistakes?
The most common mistake is forgetting both guards. Without the odd-check, you create a dp array for a fractional target. Without the range-check, you may create a negative-sized array.
// WRONG: missing guards
int P = (total + target) / 2; // could be fractional (integer division loses info)
int[] dp = new int[P + 1]; // could be negative-sized!
// CORRECT: check both guards first
if (Math.abs(target) > total) return 0;
if ((total + target) % 2 != 0) return 0;
int P = (total + target) / 2;
What should a senior engineer know?
- Pattern recognition. Target Sum is one of a family: Partition Equal Subset Sum, Count of Subset Sum, Minimum Subset Sum Difference. All reduce to 0/1 Knapsack variants.
- Counting vs boolean. The DP counts ways (dp[s] += dp[s - num]) rather than checking feasibility (dp[s] = dp[s] || dp[s - num]). The base case dp[0] = 1 represents one way to achieve zero.
- Long for large counts. For inputs where the answer exceeds Integer.MAX_VALUE, use long[] instead of int[].
- Negative target. The guards handle negative targets correctly because total + target can still be a valid non-negative even number.
Visual Overview
nums = [1, 1, 2, 3] target = 1 total = 7
Algebra:
P - N = 1
P + N = 7
────────
2P = 8 -> P = 4
Guards:
|1| <= 7 -> OK
(7+1) = 8 -> even -> OK
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=2: [1, 2, 2, 2, 1]
+num=3: [1, 2, 2, 3, 3]
Answer: dp[4] = 3
Subsets: {1a,3}, {1b,3}, {1a,1b,2}
Key Takeaway
Target Sum reduces cleanly to the counting variant of 0/1 Knapsack. I split the numbers into a positive group P and a negative group N. Their difference must equal the target and their sum must equal the total, so P = (total + target) / 2. Counting sign assignments becomes counting subsets summing to P.
Two guards protect the reduction. If total + target is odd, P would be fractional and the answer is zero. If the absolute target exceeds the total, no assignment can reach it. When the guards pass, I run the counting DP: seed dp[0] = 1 and for each number sweep sums high to low with dp[s] += dp[s - num].
The DP runs in O(n * P) time and O(P) space, far better than brute-forcing 2^n combinations. For strictly positive inputs the reduction is clean; for inputs with zeros, each zero doubles the count because it contributes nothing to the sum either way.
At the National Bank of India, the reconciliation team used this when each adjustment could be posted as a credit or debit and needed the count of valid sign choices reaching a required net position. Explaining the algebraic reduction, the two guards, and the counting recurrence shows an interviewer I can transform a signed-sum question into a 0/1 Knapsack counting problem.
Remember one sentence: reduce signs to subsets by computing P = (total + target) / 2, guard against odd and out-of-range cases, then count subsets summing to P with the standard 0/1 Knapsack DP.
---