Problem 30.2 · Knapsack DPMedium

Target Sum

What it teaches: Algebra turns ± signs into counting subsets with sum (total + target) / 2.

Practise it on judges as “Target Sum”.

The problem

Put + or − before each number. Return the number of ways the expression equals target.

Example 1

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

Constraints

1 ≤ n ≤ 20
0 ≤ nums[i] ≤ 1000
sum ≤ 1000

Pattern clues in the wording

→ Assign + or − to each number

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,1,1,1,1] target = 3	5
2	nums = [1] target = 1	1

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Counting knapsack · O(n × P)

Counting knapsack

Time O(n × P) Space O(P)

If total + target is odd or |target| > total, 0. Otherwise ways[0] = 1 and for each x, for s downwards: ways[s] += ways[s − x].

Approach 1

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int x : nums) total += x;
        if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
        int p = (total + target) / 2;
        int[] ways = new int[p + 1];
        ways[0] = 1;
        for (int x : nums)
            for (int s = p; s >= x; s--) ways[s] += ways[s - x];
        return ways[p];
    }
}

Verdict: Zeros are handled naturally (each doubles the count).

Before you submit

Edge cases and common mistakes

Test these inputs

Zeros in nums
Negative target
Target larger than total

Mistakes people make

Skipping the parity check.
Treating x = 0 specially (the downward loop already doubles counts).

Interview

Follow-up questions

And with plain recursion?

Command Palette

The problem

Approaches

Counting knapsack

Edge cases and common mistakes

Follow-up questions

Related problems