115.Target Sum

Medium2-D Dynamic Programming · 5/11

Problem

You are given an integer array nums and an integer target. Put either a '+' or a '-' sign in front of every number and concatenate them into an expression (e.g. +2 -1 +1).

Return the number of different sign assignments whose expression evaluates to target.

Examples

Input:  nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: Exactly one number gets a '-' sign, and it can be any of the 5:
             -1+1+1+1+1 = 3, +1-1+1+1+1 = 3, ..., +1+1+1+1-1 = 3

Input:  nums = [1], target = 1
Output: 1

Input:  nums = [0, 0, 1], target = 1
Output: 4
Explanation: Each 0 can be +0 or -0 independently: 2 * 2 = 4 assignments.

Constraints

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums) <= 1000
-1000 <= target <= 1000

💡 Key Insight

Split the numbers into those with + (sum P) and those with - (sum N). Then P - N = target and P + N = total, so P = (total + target) / 2. The problem becomes "count subsets of nums that sum to P" — a classic 0/1 knapsack count solvable with a single 1-D array iterated backwards. If total + target is odd or |target| > total, the answer is 0.

Recursion (Brute Force)

TimeO(2^n)SpaceO(n)

Intuition

Try both signs for every number. dfs(i, sum) = number of ways to finish from index i when the running sum is sum.

Algorithm

dfs(i, sum):
- If i == n, return 1 if sum == target else 0.
- Return dfs(i + 1, sum + nums[i]) + dfs(i + 1, sum - nums[i]).
Return dfs(0, 0).

Visualization

flowchart TD
    A["dfs(0, 0)<br/>nums [1,1], target 0"] -->|"+1"| B["dfs(1, 1)"]
    A -->|"-1"| C["dfs(1, -1)"]
    B -->|"+1"| D["sum 2 → 0"]
    B -->|"-1"| E["sum 0 → 1"]
    C -->|"+1"| F["sum 0 → 1"]
    C -->|"-1"| G["sum -2 → 0"]
    E --> H["total = 2"]
    F --> H

Code

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    private int dfs(int[] nums, int target, int i, int sum) {
        if (i == nums.length) {
            return sum == target ? 1 : 0; // one full expression built
        }
        return dfs(nums, target, i + 1, sum + nums[i])   // '+' sign
             + dfs(nums, target, i + 1, sum - nums[i]);  // '-' sign
    }
}

Complexity

Time: O(2^n) — every sign combination is enumerated (n ≤ 20, so ~10^6 — this actually passes, but it scales badly).
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n · total)SpaceO(n · total)

Intuition

The running sum always lies in [-total, total], so there are only n · (2·total + 1) states. Shift sum by total to index an array.

Algorithm

total = sum(nums); memo = new Integer[n][2 * total + 1].
Same recursion; key the cache by (i, sum + total).

Dry Run

nums = [1, 1, 1, 1, 1], target = 3, total = 5
dfs(4, 2)  = [2+1 == 3] + [2-1 == 3] = 1
dfs(4, 4)  = [5 == 3] + [3 == 3] = 1
dfs(3, 3)  = dfs(4, 4) + dfs(4, 2) = 2      ← reached from several parents, solved once
...
dfs(0, 0)  = 5

Code

java

class Solution {
    private Integer[][] memo;
    private int[] nums;
    private int target, total;

    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        for (int x : nums) {
            total += x;
        }
        memo = new Integer[nums.length][2 * total + 1];
        return dfs(0, 0);
    }

    private int dfs(int i, int sum) {
        if (i == nums.length) {
            return sum == target ? 1 : 0;
        }
        if (memo[i][sum + total] != null) {
            return memo[i][sum + total]; // offset keeps index non-negative
        }
        int ways = dfs(i + 1, sum + nums[i]) + dfs(i + 1, sum - nums[i]);
        memo[i][sum + total] = ways;
        return ways;
    }
}

Complexity

Time: O(n · total) — each (i, sum) state once.
Space: O(n · total) — the memo table.

Bottom-Up 2-D Tabulation

TimeO(n · total).SpaceO(n · total).

Intuition

Let dp[i][s + total] = number of ways the first i numbers can produce sum s. Each number pushes every reachable sum both up and down.

Recurrence: dp[i][s] = dp[i-1][s - nums[i-1]] + dp[i-1][s + nums[i-1]], with dp[0][0] = 1.

Algorithm

If |target| > total, return 0.
dp = new int[n + 1][2 * total + 1], dp[0][total] = 1 (sum 0).
For each i, for each reachable s in row i - 1, add its count to s + nums[i-1] and s - nums[i-1] in row i.
Return dp[n][target + total].

Dry Run

nums = [1, 1, 1, 1, 1], target = 3 (only non-zero entries shown):

i	-5	-4	-3	-2	-1	0	1	2	3	4	5
0						1
1					1		1
2				1		2		1
3			1		3		3		1
4		1		4		6		4		1
5	1		5		10		10		5		1

Code

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        if (Math.abs(target) > total) {
            return 0; // unreachable
        }
        int n = nums.length, width = 2 * total + 1;
        int[][] dp = new int[n + 1][width];
        dp[0][total] = 1; // sum 0 with no numbers (offset by total)
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = 0; s < width; s++) {
                if (dp[i - 1][s] == 0) {
                    continue;
                }
                dp[i][s + x] += dp[i - 1][s]; // '+' sign
                dp[i][s - x] += dp[i - 1][s]; // '-' sign
            }
        }
        return dp[n][target + total];
    }
}

Complexity

Time: O(n · total).
Space: O(n · total).

Subset-Sum 1-D DPOptimal

TimeO(n · P) where P ≤ totalSpaceO(P)

Intuition

From the key insight, we need the number of subsets summing to P = (total + target) / 2. Classic 0/1 knapsack counting: dp[j] = number of subsets (of the numbers processed so far) that sum to j. For each number x, iterate j downward so that dp[j - x] still refers to subsets that do not include x — each number is used at most once.

Recurrence: dp[j] += dp[j - x] for j from P down to x.

Zeros are handled naturally: for x = 0, dp[j] += dp[j] doubles every count, matching the +0 / -0 choice.

Algorithm

total = sum(nums). If |target| > total or (total + target) is odd, return 0.
P = (total + target) / 2; dp = new int[P + 1]; dp[0] = 1.
For each x in nums: for j = P down to x: dp[j] += dp[j - x].
Return dp[P].

Dry Run

flowchart TD
    A["total=5, target=3<br/>P = (5+3)/2 = 4"] --> B["dp = [1,0,0,0,0]"]
    B -->|"x=1"| C["[1,1,0,0,0]"]
    C -->|"x=1"| D["[1,2,1,0,0]"]
    D -->|"x=1"| E["[1,3,3,1,0]"]
    E -->|"x=1"| F["[1,4,6,4,1]"]
    F -->|"x=1"| G["[1,5,10,10,5]"]
    G --> H["answer dp[4] = 5"]

Code

java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        // P - N = target, P + N = total  =>  P = (total + target) / 2
        if (Math.abs(target) > total || (total + target) % 2 != 0) {
            return 0;
        }
        int p = (total + target) / 2;
        int[] dp = new int[p + 1];
        dp[0] = 1; // empty subset
        for (int x : nums) {
            for (int j = p; j >= x; j--) { // downward: each number used once
                dp[j] += dp[j - x];
            }
        }
        return dp[p];
    }
}

Complexity

Time: O(n · P) where P ≤ total — one backward sweep per number.
Space: O(P) — one array.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2^n)	O(n)
Top-Down Memoization	O(n · total)	O(n · total)
Bottom-Up 2-D Tabulation	O(n · total)	O(n · total)
Subset-Sum 1-D DP	O(n · total)	O(total)

Common Pitfalls

Forgetting the parity check: if total + target is odd, no subset works — return 0 (otherwise integer division silently rounds).
Not checking |target| > total — P becomes negative (array size error) or exceeds total (index out of bounds in the 2-D table).
Iterating j upward in the 1-D knapsack — numbers get reused, overcounting.
Indexing memo by a raw negative sum — offset by total.
Treating 0s specially or skipping them — each zero doubles the count, and the DP already handles it.