Target sum: count sign assignments that reach a target

Given an array of non-negative integers and a target T, put a + or - in front of every number. Count how many sign assignments make the expression equal T. Two assignments are different if any position gets a different sign, even when the numbers are equal. Write the recursive solution with memoization, then the iterative dynamic program, and compare them.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_ways(nums: list[int], target: int) -> int

Example

count_ways([1, 1, 1, 1, 1], 3)  ->  5   # one of the five 1s gets the minus sign
count_ways([1], 1)              ->  1
count_ways([0, 0, 1], 1)        ->  4   # each 0 can be +0 or -0
count_ways([2, 3], 4)           ->  0

Constraints

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

Clarifying questions

• Do signs on zeros count as different assignments?
• Can the target be negative or larger than the total?
• Do you also need one valid assignment, or only the count?

What a strong answer covers

• Recursion over (index, running sum) with memoization: O(n · S) states for S = sum(nums), with an offset or a dict for negative sums.
• The reduction: if P gets plus signs, sum(P) = (total + T) / 2; it is 0 ways when that is odd or |T| > total. Then a 0/1 knapsack count over subset sums, iterating sums downward, O(n · S) time and O(S) space.
• How zeros are handled (each one doubles the count) and why the DP does that by itself.
• Recovering one valid assignment by walking back through a 2-D table.

Follow-ups

• Return one assignment that works, or all of them.
• The numbers can be negative.
• Sums are too large for a table: meet in the middle over the two halves.