Target Sum

Problem

You are given a list of non-negative integers nums and an integer target. For every element you must choose a sign, + or -, and then add up the signed values. Count how many distinct sign assignments make the total equal to target. Two assignments are different if they differ in the sign of at least one position, even when the element values are equal.

• nums holds up to twenty non-negative integers, and their sum stays within a moderate range (at most a thousand or so).
• target can be negative and is within the same rough magnitude.

Examples

• nums = [2, 2, 2, 2, 2], target = 2 → 10. Exactly two of the five 2s get a minus sign, since 10 - 2*(2+2) = 2, and there are C(5, 2) = 10 ways to choose which two.
• nums = [3], target = 3 → 1. Only +3 works.
• nums = [2, 3], target = 6 → 0. The largest achievable total is 5.

Hints

1. Separate the elements into the ones you add and the ones you subtract. Write the total in terms of the sum of each group.
2. Since the two groups together sum to sum(nums), the total is determined entirely by the sum of the positive group. What must that sum be?
3. Count the subsets with sum (sum(nums) + target) / 2 using 0/1 knapsack counting with the inner loop descending.