230. Target Sum
🔗 LeetCode Problem: 494. Target Sum
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, Backtracking, DP - Subsequences
Problem Statement
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints:
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
🌳 Visual Understanding - Using nums = [1, 1, 1, 1, 1], target = 3
The Problem We're Solving:
Given: nums = [1, 1, 1, 1, 1], target = 3
Goal: Count ways to assign +/- signs to make sum = 3
For each number, we have 2 choices:
- Add it (+)
- Subtract it (-)
Question: How many different sign assignments
result in sum = 3? 🤔
Finding All Expressions:
Array: [1, 1, 1, 1, 1]
Target: 3
Expression 1: -1 + 1 + 1 + 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sign choices: [-, +, +, +, +]
Sum: -1 + 1 + 1 + 1 + 1 = 3 ✓
Expression 2: +1 - 1 + 1 + 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sign choices: [+, -, +, +, +]
Sum: 1 - 1 + 1 + 1 + 1 = 3 ✓
Expression 3: +1 + 1 - 1 + 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sign choices: [+, +, -, +, +]
Sum: 1 + 1 - 1 + 1 + 1 = 3 ✓
Expression 4: +1 + 1 + 1 - 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sign choices: [+, +, +, -, +]
Sum: 1 + 1 + 1 - 1 + 1 = 3 ✓
Expression 5: +1 + 1 + 1 + 1 - 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sign choices: [+, +, +, +, -]
Sum: 1 + 1 + 1 + 1 - 1 = 3 ✓
Total: 5 different ways ✓
Answer: 5
Why This Is Interesting:
At first glance: Looks like brute force problem
Try all 2^n sign combinations
Count those that sum to target
But there's a BEAUTIFUL transformation! 🔑
Think about it differently:
Some numbers get + sign (positive set P)
Some numbers get - sign (negative set N)
Result: sum(P) - sum(N) = target
But we know:
sum(P) + sum(N) = total_sum (all numbers)
From these two equations:
sum(P) - sum(N) = target
sum(P) + sum(N) = total_sum
Add them: 2 × sum(P) = target + total_sum
Therefore: sum(P) = (target + total_sum) / 2
WOW! This becomes Subset Sum problem! 🎯
🧠 The AHA Moment - The Beautiful Transformation
Understanding Why sum(P) - sum(N) = target
First, let's understand what this equation means:
When we assign + or - signs to numbers:
- P (Positive set) = numbers we put + in front of
- N (Negative set) = numbers we put - in front of
Example: nums = [1, 1, 1, 1, 1], target = 3
Expression: +1 +1 +1 +1 -1 = 3
Identify P and N:
P = {1, 1, 1, 1} (four 1's with + sign)
N = {1} (one 1 with - sign)
Calculate:
sum(P) = 1 + 1 + 1 + 1 = 4
sum(N) = 1
sum(P) - sum(N) = 4 - 1 = 3 ✓ (equals target!)
Another expression: -1 +1 +1 +1 +1 = 3
P = {1, 1, 1, 1}
N = {1}
sum(P) - sum(N) = 4 - 1 = 3 ✓
Why does sum(P) - sum(N) equal the expression result?
When you write: +1 +1 -1 +1 +1
You're calculating:
(+1) + (+1) + (-1) + (+1) + (+1)
= (1 + 1 + 1 + 1) + (-1)
= (sum of positive numbers) - (sum of negative numbers)
= sum(P) - sum(N)
= 4 - 1
= 3
This is fundamental arithmetic:
Adding positive numbers → contributes positively
Adding negative numbers → contributes negatively
Final result = positive contributions - negative contributions
Verify all 5 expressions for nums = [1,1,1,1,1], target = 3:
┌───────────────┬──────────────┬──────────────┬────────┬────────┬─────────────────┐
│ Expression │ P (positive) │ N (negative) │ sum(P) │ sum(N) │ sum(P) - sum(N) │
├───────────────┼──────────────┼──────────────┼────────┼────────┼─────────────────┤
│ -1+1+1+1+1 │ {1,1,1,1} │ {1} │ 4 │ 1 │ 4-1=3 ✓ │
│ +1-1+1+1+1 │ {1,1,1,1} │ {1} │ 4 │ 1 │ 4-1=3 ✓ │
│ +1+1-1+1+1 │ {1,1,1,1} │ {1} │ 4 │ 1 │ 4-1=3 ✓ │
│ +1+1+1-1+1 │ {1,1,1,1} │ {1} │ 4 │ 1 │ 4-1=3 ✓ │
│ +1+1+1+1-1 │ {1,1,1,1} │ {1} │ 4 │ 1 │ 4-1=3 ✓ │
└───────────────┴──────────────┴──────────────┴────────┴────────┴─────────────────┘
Notice: In ALL cases, sum(P) = 4 and sum(N) = 1!
Every valid expression MUST satisfy: sum(P) - sum(N) = target
The KEY Insight - Transform to Subset Sum:
Now we have two equations:
Equation 1: sum(P) - sum(N) = target (must be true for valid expression)
Equation 2: sum(P) + sum(N) = total (P and N together = all numbers)
Let's solve for sum(P):
sum(P) - sum(N) = target ... (1)
sum(P) + sum(N) = total ... (2)
Add equations (1) and (2):
sum(P) - sum(N) + sum(P) + sum(N) = target + total
2 × sum(P) = target + total
sum(P) = (target + total) / 2
WOW! This is the transformation! 🎯
The Beautiful Insight:
ORIGINAL PROBLEM:
"Count ways to assign +/- to make target"
Seems like we need to track all signs! 😰
Need to try 2^n combinations!
TRANSFORMED PROBLEM:
"Count subsets that sum to (target + total) / 2"
Much simpler! Just find subsets! 😊
This is a standard DP problem!
Why this works:
Every valid +/- assignment creates a partition:
P = numbers with + sign
N = numbers with - sign
And sum(P) must equal (target + total) / 2
So: counting +/- assignments = counting subsets of sum (target + total) / 2
Detailed Transformation Example:
nums = [1, 1, 1, 1, 1], target = 3
Step 1: Calculate required subset sum
total = 5
sum(P) = (3 + 5) / 2 = 4
Step 2: Question becomes "How many ways to select numbers summing to 4?"
Step 3: Verify the correspondence:
Subset {1,1,1,1} at indices {0,1,2,3}:
sum = 4 ✓
Remaining {1} at index {4}: sum = 1
Expression: +1+1+1+1-1 = (4) - (1) = 3 ✓
Subset {1,1,1,1} at indices {0,1,2,4}:
sum = 4 ✓
Remaining {1} at index {3}: sum = 1
Expression: +1+1+1-1+1 = (4) - (1) = 3 ✓
Subset {1,1,1,1} at indices {0,1,3,4}:
sum = 4 ✓
Remaining {1} at index {2}: sum = 1
Expression: +1+1-1+1+1 = (4) - (1) = 3 ✓
Subset {1,1,1,1} at indices {0,2,3,4}:
sum = 4 ✓
Remaining {1} at index {1}: sum = 1
Expression: +1-1+1+1+1 = (4) - (1) = 3 ✓
Subset {1,1,1,1} at indices {1,2,3,4}:
sum = 4 ✓
Remaining {1} at index {0}: sum = 1
Expression: -1+1+1+1+1 = (4) - (1) = 3 ✓
5 subsets summing to 4 = 5 ways to make target 3!
Each subset corresponds to exactly ONE +/- assignment! 🎯
When Transformation is IMPOSSIBLE:
RULE 1: If (target + total) is ODD → impossible!
Can't have fractional subset sum
Example: target=4, total=5 → need sum = 4.5 ✗
RULE 2: If target > total → impossible!
Can't make target larger than all positives
Example: target=10, total=5 → impossible ✗
RULE 3: If target < -total → impossible!
Can't make target smaller than all negatives
Example: target=-10, total=5 → impossible ✗
Must check these before solving! 🔑
🔴 Approach 1: Brute Force (Try All Sign Assignments)
📐 Function Definition
Function Signature:
int findTargetSumWays(int[] nums, int target)
What it represents:
Input Parameter nums:
- Array of non-negative integers
- Each number gets + or - sign
- Example: nums = [1, 1, 1, 1, 1]
Input Parameter target:
- Target sum to achieve
- Example: target = 3
Return Value (int): - Number of ways to assign signs - Each way must sum to target - Example: 5
Purpose: - For each number: try + and try - - Recursively explore all 2^n combinations - Count combinations that sum to target
Key Understanding:
For each number, two choices:
Add it → current_sum + num
Subtract it → current_sum - num
Try ALL combinations recursively!
💡 Intuition
The simplest idea: Try all sign assignments!
Think of it like a decision tree:
Array: [1, 1, 1, 1, 1]
Target: 3
Decision tree:
Start (sum=0)
/ \
+1 (sum=1) -1 (sum=-1)
/ \ / \
+1(2) -1(0) +1(0) -1(-2)
... ... ... ...
At each number:
- Add it: sum += num
- Subtract it: sum -= num
At the end (processed all numbers):
If sum == target: count++
Try ALL 2^n paths! 🎯
📝 Implementation
class Solution {
public int findTargetSumWays(int[] nums, int target) {
return helper(nums, 0, 0, target);
}
private int helper(int[] nums, int index, int currentSum, int target) {
// Base case: processed all numbers
if (index == nums.length) {
return currentSum == target ? 1 : 0;
}
// Choice 1: Add current number
int add = helper(nums, index + 1, currentSum + nums[index], target);
// Choice 2: Subtract current number
int subtract = helper(nums, index + 1, currentSum - nums[index], target);
return add + subtract;
}
}
🔍 Detailed Dry Run: nums = [1, 1, 1], target = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(nums, 0, 0, 1) - Process nums[0]=1
│
├─ Add 1: helper(nums, 1, 1, 1)
│ │
│ ├─ Add 1: helper(nums, 2, 2, 1)
│ │ │
│ │ ├─ Add 1: helper(nums, 3, 3, 1)
│ │ │ sum=3, target=1 → return 0
│ │ │
│ │ └─ Subtract 1: helper(nums, 3, 1, 1)
│ │ sum=1, target=1 → return 1 ✓
│ │ Expression: +1+1-1 = 1
│ │
│ │ Total: 0 + 1 = 1
│ │
│ └─ Subtract 1: helper(nums, 2, 0, 1)
│ │
│ ├─ Add 1: helper(nums, 3, 1, 1)
│ │ sum=1, target=1 → return 1 ✓
│ │ Expression: +1-1+1 = 1
│ │
│ └─ Subtract 1: helper(nums, 3, -1, 1)
│ sum=-1, target=1 → return 0
│
│ Total: 1 + 0 = 1
│
│ Total from add: 1 + 1 = 2
│
└─ Subtract 1: helper(nums, 1, -1, 1)
│
├─ Add 1: helper(nums, 2, 0, 1)
│ │
│ ├─ Add 1: helper(nums, 3, 1, 1)
│ │ sum=1, target=1 → return 1 ✓
│ │ Expression: -1+1+1 = 1
│ │
│ └─ Subtract 1: helper(nums, 3, -1, 1)
│ sum=-1, target=1 → return 0
│
│ Total: 1 + 0 = 1
│
└─ Subtract 1: helper(nums, 2, -2, 1)
│
├─ Add 1: helper(nums, 3, -1, 1)
│ sum=-1, target=1 → return 0
│
└─ Subtract 1: helper(nums, 3, -3, 1)
sum=-3, target=1 → return 0
Total: 0 + 0 = 0
Total from subtract: 1 + 0 = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT: 2 + 1 = 3 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
All 3 ways found:
+1 + 1 - 1 = 1 ✓
+1 - 1 + 1 = 1 ✓
-1 + 1 + 1 = 1 ✓
Why This Is Slow:
Decision tree has 2^n paths
For each number: 2 choices (+ or -)
Total combinations: 2^n
Example:
n = 5: 2^5 = 32 paths
n = 10: 2^10 = 1,024 paths
n = 20: 2^20 = 1,048,576 paths
Many paths explore same (index, sum) states!
This is why brute force is TOO SLOW! ❌
📊 Complexity Analysis
Time Complexity: O(2^n)
n = length of nums array
At each number: 2 choices
Total paths: 2^n
For n = 20: 1,048,576 operations
Manageable but not optimal! ⚠️
Space Complexity: O(n)
Recursion stack depth
Maximum depth = n
Why This Is Slow:
❌ Tries every sign combination
❌ Repeats same (index, sum) states
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Subset Sum Transformation + DP
📐 Function Definition
Function Signature:
int findTargetSumWays(int[] nums, int target)
What it represents:
DP Array:
- dp[i] = Number of ways to make sum i using available numbers
- Build from dp[0], dp[1], ..., up to dp[targetSum]
- This is Combination Sum IV pattern!
Purpose: - Transform problem to: "Count subsets summing to (target + total) / 2" - Use DP to count subsets (allows duplicates!) - Return count
Key Understanding:
Original: Count +/- assignments making target
Transformed: Count subsets summing to (target + total) / 2
This is exactly Combination Sum IV!
💡 Intuition
The brilliant idea: Transform to subset sum!
Mathematical insight:
Let P = numbers with + sign
Let N = numbers with - sign
We want: sum(P) - sum(N) = target
We know: sum(P) + sum(N) = total
Add equations:
2 × sum(P) = target + total
sum(P) = (target + total) / 2
So counting +/- assignments = counting subsets!
Example: nums = [1,1,1,1,1], target = 3
total = 5
Need: sum(P) = (3 + 5) / 2 = 4
Count subsets summing to 4 = answer!
📝 Implementation
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
// Check if transformation is valid
if ((target + totalSum) % 2 != 0) {
return 0; // Can't have fractional subset sum
}
if (Math.abs(target) > totalSum) {
return 0; // Target out of range
}
int targetSum = (target + totalSum) / 2;
// dp[i] = number of ways to make sum i
int[] dp = new int[targetSum + 1];
dp[0] = 1; // One way to make 0: empty subset
// Process each number
for (int num : nums) {
// Traverse right to left (0/1 knapsack optimization)
for (int j = targetSum; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[targetSum];
}
}
🔍 Detailed Dry Run: nums = [1, 1, 1, 1, 1], target = 3
totalSum = 5
target + totalSum = 3 + 5 = 8 (even ✓)
targetSum = 8 / 2 = 4
dp = [1, 0, 0, 0, 0]
0 1 2 3 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS EACH NUMBER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process num = 1 (first occurrence):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 4 to 1 (right to left):
j=4: dp[4] += dp[3] = 0 + 0 = 0
j=3: dp[3] += dp[2] = 0 + 0 = 0
j=2: dp[2] += dp[1] = 0 + 0 = 0
j=1: dp[1] += dp[0] = 0 + 1 = 1 ✓
dp = [1, 1, 0, 0, 0]
Process num = 1 (second occurrence):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 4 to 1:
j=4: dp[4] += dp[3] = 0 + 0 = 0
j=3: dp[3] += dp[2] = 0 + 0 = 0
j=2: dp[2] += dp[1] = 0 + 1 = 1 ✓
j=1: dp[1] += dp[0] = 1 + 1 = 2 ✓
dp = [1, 2, 1, 0, 0]
Process num = 1 (third occurrence):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 4 to 1:
j=4: dp[4] += dp[3] = 0 + 0 = 0
j=3: dp[3] += dp[2] = 0 + 1 = 1 ✓
j=2: dp[2] += dp[1] = 1 + 2 = 3 ✓
j=1: dp[1] += dp[0] = 2 + 1 = 3 ✓
dp = [1, 3, 3, 1, 0]
Process num = 1 (fourth occurrence):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 4 to 1:
j=4: dp[4] += dp[3] = 0 + 1 = 1 ✓
j=3: dp[3] += dp[2] = 1 + 3 = 4 ✓
j=2: dp[2] += dp[1] = 3 + 3 = 6 ✓
j=1: dp[1] += dp[0] = 3 + 1 = 4 ✓
dp = [1, 4, 6, 4, 1]
Process num = 1 (fifth occurrence):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 4 to 1:
j=4: dp[4] += dp[3] = 1 + 4 = 5 ✓
j=3: dp[3] += dp[2] = 4 + 6 = 10 ✓
j=2: dp[2] += dp[1] = 6 + 4 = 10 ✓
j=1: dp[1] += dp[0] = 4 + 1 = 5 ✓
dp = [1, 5, 10, 10, 5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP ARRAY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [1, 5, 10, 10, 5]
0 1 2 3 4
Interpretation:
dp[0] = 1 (empty subset)
dp[1] = 5 (5 ways to make sum 1)
dp[2] = 10 (10 ways to make sum 2)
dp[3] = 10 (10 ways to make sum 3)
dp[4] = 5 (5 ways to make sum 4) ✓
Answer: dp[4] = 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 5 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
This means there are 5 ways to select numbers summing to 4.
Each way corresponds to one +/- assignment making target 3!
Why This Works - The Magic:
Beautiful correspondence:
Subset summing to 4:
{1,1,1,1} - indices {0,1,2,3}
Remaining {1} - index {4}
Expression: +1+1+1+1-1 = 3 ✓
Another subset summing to 4:
{1,1,1,1} - indices {0,1,2,4}
Remaining {1} - index {3}
Expression: +1+1+1-1+1 = 3 ✓
Each subset of sum 4 = one +/- assignment!
The DP counts ALL such subsets including duplicates! 🎯
📊 Complexity Analysis
Time Complexity: O(n × targetSum)
n = length of nums
targetSum = (target + totalSum) / 2
Outer loop: n iterations
Inner loop: targetSum iterations
Total: O(n × targetSum)
For n = 20, targetSum = 500:
20 × 500 = 10,000 operations
MUCH better than 2^20! ✓
Space Complexity: O(targetSum)
DP array of size targetSum + 1
Optimal space! ✓
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ TARGET SUM - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ O(2^n) │ O(n) │ High │ Start │
│ Subset DP │ O(n×tgt) │ O(tgt) │ Best ✓ │ Best ✓ │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
tgt = (target + totalSum) / 2
For interviews: Show transformation insight!
💻 Complete Working Code
class Solution {
public int findTargetSumWays(int[] nums, int target) {
return subsetSum(nums, target);
}
// Approach: Subset Sum DP - O(n×targetSum) time, O(targetSum) space
private int subsetSum(int[] nums, int target) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if ((target + totalSum) % 2 != 0 || Math.abs(target) > totalSum) {
return 0;
}
int targetSum = (target + totalSum) / 2;
int[] dp = new int[targetSum + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = targetSum; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[targetSum];
}
// Approach 1: Brute Force - O(2^n) time
private int bruteForce(int[] nums, int target) {
return helperBrute(nums, 0, 0, target);
}
private int helperBrute(int[] nums, int index, int currentSum, int target) {
if (index == nums.length) {
return currentSum == target ? 1 : 0;
}
int add = helperBrute(nums, index + 1, currentSum + nums[index], target);
int subtract = helperBrute(nums, index + 1, currentSum - nums[index], target);
return add + subtract;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findTargetSumWays(new int[] { 1, 1, 1, 1, 1 }, 3) == 5);
System.out.println(s.findTargetSumWays(new int[] { 1 }, 1) == 1);
}
}
🔑 Key Insights
The Beautiful Transformation:
ORIGINAL PROBLEM:
"Count +/- assignments making target"
TRANSFORMED PROBLEM:
"Count subsets summing to (target + total) / 2"
This is THE key insight! 🔑
Math proof:
sum(P) - sum(N) = target
sum(P) + sum(N) = total
2 × sum(P) = target + total
sum(P) = (target + total) / 2
Counting +/- signs = counting subsets!
Early Termination Checks:
RULE 1: (target + total) must be EVEN
Otherwise sum(P) is fractional
RULE 2: |target| ≤ total
Can't exceed range [-total, total]
These checks save computation! ✓
Pattern Recognition:
This problem appears as:
- Backtracking (try all +/- combinations)
- Subset Sum (the transformation!)
Subset Sum is most elegant! 🎯
Why Right-to-Left:
In DP: dp[j] += dp[j - num]
Right to left ensures:
- Use OLD dp[j - num] (before update)
- Each number used at most once
This preserves 0/1 knapsack property!
🎪 Memory Aid
"Transform: +/- signs → subset sum!"
"sum(P) = (target + total) / 2!"
"Count subsets with duplicates allowed!"
"Right to left for 0/1 property!" ✨
⚠️ Common Mistakes
- ❌ Not checking if (target + total) is even
- ❌ Not checking if target is in valid range
- ❌ Treating as regular subset sum (this counts WITH duplicates!)
- ❌ Processing left to right in DP (uses number multiple times!)
- ❌ Not understanding the transformation
✅ Interview Talking Points
"This problem has a beautiful mathematical transformation.
Initial approach:
Try all 2^n combinations of +/- signs
Count those summing to target
Key insight - Mathematical transformation:
Let P = numbers with +, N = numbers with -
We want: sum(P) - sum(N) = target
We know: sum(P) + sum(N) = total
Add equations: 2×sum(P) = target + total
Therefore: sum(P) = (target + total) / 2
Problem transforms to:
'Count subsets summing to (target + total) / 2'
This is Subset Sum with duplicates!
Early optimizations:
- If (target + total) is odd → impossible
- If |target| > total → impossible
DP Approach:
dp[i] = number of ways to make sum i
Base: dp[0] = 1
For each number:
For j from targetSum down to num:
dp[j] += dp[j - num]
Process right-to-left (0/1 property)
Complexity: O(n × targetSum) time, O(targetSum) space
Much better than O(2^n) brute force!
This transformation is the elegant solution!"
📝 Quick Revision Notes
⚡ Quick Implementation
public class Solution {
public int findTargetSumWays(int[] a, int k) {
// return recursive_difficult(a, 0, 0, k);
// Above above approach will not be straight way converted to top down or bottom
// up as k will be negative
int p = 0; // sum of only +ve numbers
int n = 0; // sum of only -ve numbers
int total = 0; // sum of all numbers with abs applied
for (int num : a) {
if (num > 0) {
p += num;
} else if (num < 0) {
n += num;
}
total += Math.abs(num);
}
if (total < Math.abs(k) || (k + total) % 2 != 0) {
return 0;
}
// p - n = k (required) and p + n = total (above is calculated)
// p = (k+total)/2 => which is always +ve and no worry.
int newK = (k + total) / 2;
// return recursive(a, 0, newK);
// Integer[][] memo = new Integer[a.length + 1][newK + 1];
// return topDown(a, 0, newK, memo);
return bottomUp(a, newK);
}
private int bottomUp(int[] a, int k) {
int len = a.length;
int[][] dp = new int[len + 1][k + 1];
dp[len][0] = 1;
for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
dp[i][j] = dp[i + 1][j];
if (j - a[i] >= 0) {
dp[i][j] += dp[i + 1][j - a[i]];
}
}
}
return dp[0][k];
}
private int topDown(int[] a, int index, int k, Integer[][] memo) {
if (index == a.length && k == 0) {
return 1;
}
if (index == a.length || k < 0) {
return 0;
}
if (memo[index][k] != null) {
return memo[index][k];
}
int take = 0;
if (k - a[index] >= 0) {
take = topDown(a, index + 1, k - a[index], memo);
}
int no_take = topDown(a, index + 1, k, memo);
return memo[index][k] = take + no_take;
}
private int recursive(int[] a, int index, int k) {
// step 4: base case
// we need to cover up entire array.
if (index == a.length && k == 0) {
return 1;
}
if (index == a.length) {
return 0;
}
// step 1: consider the number at current index and proceed to next index
int take = recursive(a, index + 1, k - a[index]);
// step 2: skip the number at current index and proceed to next index
int no_take = recursive(a, index + 1, k);
// step 3: return total ways
return take + no_take;
}
private int recursive_difficult(int[] a, int index, int curr_sum, int k) {
// step 4: base case 1
// built up sum (curr_sum) should become equal to k and
// all array should be covered (no partial cover)
if (curr_sum == k && index == a.length) {
return 1;
}
// step 4: base case 2
// if in above base case, 1st condition is not satisfied, but reached
// end of array with no more elements to be considered, returns 0.
if (index == a.length) {
return 0;
}
// step 1: consider + and proceed to next index
int plus = recursive_difficult(a, index + 1, curr_sum + a[index], k);
// step 1: consider - and proceed to next index
int minus = recursive_difficult(a, index + 1, curr_sum - a[index], k);
// step 3: return the result of both
return plus + minus;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findTargetSumWays(new int[] { 1, 1, 1, 1, 1 }, 3) == 5);
System.out.println(s.findTargetSumWays(new int[] { 1 }, 1) == 1);
System.out.println(s.findTargetSumWays(new int[] { 1 }, 2) == 0);
System.out.println(s.findTargetSumWays(new int[] { 1, 2, 1 }, 0) == 2);
System.out.println(s.findTargetSumWays(new int[] { 7, 9, 3, 8, 0, 2, 4, 8, 3, 9 }, 0) == 0);
}
}
🎉 Congratulations!
🎉 Congratulations!
You've mastered Target Sum - the elegant transformation problem!
What You Learned:
✅ Problem transformation - +/- signs → subset sum
✅ Mathematical insight - Deriving sum(P) = (target + total) / 2
✅ Early termination - Parity and range checks
✅ Brute force - Try all 2^n sign combinations
✅ Subset Sum DP - Count with duplicates
✅ Space optimization - Right-to-left processing
This is one of the most elegant DP transformations! 🚀✨