Target Sum

The problem

Put a plus sign or a minus sign in front of every number in nums, then add the signed numbers up. Return the number of ways to choose the signs so that the result is exactly target. Two ways are different when at least one position gets a different sign, even if the number there is 0. target may be negative. If no choice of signs gives target, return 0.

What to write

function solve(nums: number[], target: number): number

Input
nums = [1,1,1,1,1]
target = 3

Output
5

Input
nums = [1]
target = 1

Output
1

Constraints

Entries are nonnegative; 1 ≤ nums.length ≤ 20.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 20 numbers, so at most 2 to the power 20 = 1048576 ways to place the signs. Every result lies between minus the total of nums and plus that total. When that range is small, many different sign choices end on the same sum.

2. Hint 2: Ask a smaller question

   Take the numbers 1, 1, 1 and target 1. After signs for the first two numbers you stand at 2, 0 or -2. Does the third number care which signs brought you to 0, or only that you are at 0? How many sign choices lead to 0?

3. Hint 3: Name the pattern

   What can still happen depends only on the sum so far, not on the signs behind it. Take the numbers one at a time and keep, for every sum reached so far, how many sign choices reach it. Items decided one at a time against a running sum is knapsack dynamic programming, named after packing a bag item by item. Read the lesson on knapsack dynamic programming.

4. Hint 4: State the invariant

   Keep a table from sum to count. After k numbers have a sign, it has one entry for every sum those k numbers can produce, holding how many sign choices produce that sum. Each choice is counted exactly once, so the counts always add up to 2 to the power k.

5. Hint 5: Sketch the pseudocode

   table = one entry, sum 0 with count 1. For each number: new = empty table; for every sum and count in table, add count to new[sum + number] and to new[sum - number], a missing entry counting as 0; then table = new. Return table[target], or 0 if there is no such entry.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Map each reachable sum to its number of assignments. For every number, branch to both plus and minus, including two choices for zero.

The slow way

Try every way to place the signs: each number is added or subtracted, so n numbers give 2 to the power n sign choices. Work out each total and count those equal to target. It is correct, but the work doubles with every extra number: 5 numbers need 32 totals, 20 numbers need 1048576.

The insight

Different sign choices can reach the same sum, and from there on they behave alike: what the remaining numbers can add or take away depends only on the sum so far. So merge them into one entry, a sum and how many choices reach it, and move the whole group forward at once. Filling a table of sums number by number is knapsack dynamic programming.

Step by step

1. Start with one entry: the sum 0, reached in one way. The table maps a sum to the number of sign choices that reach it: a dictionary in Python, a Map in JavaScript. Before any number has a sign, the only sum is 0, reached in one way.
2. For each number, begin an empty table for the sums after it. Every sign choice so far gets one more sign, so the old entries all move. A separate table keeps old and new apart: a count written for this number is never read as if it were an old one.
3. From every sum reached so far, go on with a plus and with a minus. Each choice behind the old sum continues two ways: plus lands on the old sum plus the number, minus on the old sum minus the number. With a 0 both land on the same sum, and both count.
4. Add the old sum's ways to the ways of the new sum. Several old sums can land on the same new sum, so the entry is added to, never overwritten. A new sum that has no entry yet counts as 0 before the addition.
5. The new table takes the place of the old one. The old table describes the numbers before this one and is not needed again: the next number builds only on the new table. So at most two tables exist at any moment.
6. Return the ways stored for target, or 0 when it has no entry. After the last number the table covers every sign choice for the whole list. A target that no choice reaches never got an entry, so a plain lookup would fail or return nothing. The answer for that case is 0.

The same numbered steps are the comments in each solution.

function solve(nums, target) {
  // 1. Start with one entry: the sum 0, reached in one way
  let counts = new Map([[0, 1]]);
  // 2. For each number, begin an empty table for the sums after it
  for (const n of nums) {
    const next = new Map();
    // 3. From every sum reached so far, go on with a plus and with a minus
    for (const [sum, count] of counts)
      for (const s of [sum + n, sum - n])
        // 4. Add the old sum's ways to the ways of the new sum
        next.set(s, (next.get(s) || 0) + count);
    // 5. The new table takes the place of the old one
    counts = next;
  }
  // 6. Return the ways stored for target, or 0 when it has no entry
  return counts.get(target) || 0;
}

function solve(nums: number[], target: number): number {
  // 1. Start with one entry: the sum 0, reached in one way
  let counts = new Map([[0, 1]]);
  // 2. For each number, begin an empty table for the sums after it
  for (const n of nums) {
    const next = new Map<number, number>();
    // 3. From every sum reached so far, go on with a plus and with a minus
    for (const [sum, count] of counts)
      for (const s of [sum + n, sum - n])
        // 4. Add the old sum's ways to the ways of the new sum
        next.set(s, (next.get(s) || 0) + count);
    // 5. The new table takes the place of the old one
    counts = next;
  }
  // 6. Return the ways stored for target, or 0 when it has no entry
  return counts.get(target) || 0;
}

def solve(nums, target):
    # 1. Start with one entry: the sum 0, reached in one way
    counts = {0: 1}
    # 2. For each number, begin an empty table for the sums after it
    for num in nums:
        next_counts = {}
        # 3. From every sum reached so far, go on with a plus and with a minus
        for total, count in counts.items():
            for new_total in (total + num, total - num):
                # 4. Add the old sum's ways to the ways of the new sum
                next_counts[new_total] = next_counts.get(new_total, 0) + count
        # 5. The new table takes the place of the old one
        counts = next_counts
    # 6. Return the ways stored for target, or 0 when it has no entry
    return counts.get(target, 0)

Example 1, traced

Input
nums = [1,1,1,1,1]
target = 3

Output
5

Why it works

Before any number, sum 0 is reached in one way. Every sign choice for one more number is an earlier choice plus one more sign, so exactly one old entry carries that choice to exactly one new sum. So after each number the table counts every sign choice once, under the sum that choice produces, and the entry for target is the answer.

Time and space

Time O(n · sum(nums)), extra space O(sum(nums)). Every sum lies between minus and plus the total of nums, so a table never has more than 2 × total + 1 entries. Each of the n numbers visits every entry once, which gives O(n · sum(nums)) time. At most two tables exist, so the space is O(sum(nums)).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• A 0 has two signs. Plus 0 and minus 0 give the same sum, but they are two sign choices and both count. Counting them once turns the answer for 0, 0, 1 with target 1 from 4 into 1.
• Add to the new entry, do not overwrite it. Two old sums can land on the same new sum, and both groups of ways count. With overwriting, five 1s with target 3 return 1 instead of 5.
• The target may have no entry at all, as for 1, 2 with target 0. Look it up with a default of 0. A plain lookup raises an error in Python and returns undefined in JavaScript.

Pattern

Knapsack dynamic programming. Builds on Partition Equal Subset Sum and Coin Change II.

Keep going