Target sum assignments

Count ways to assign + and - signs to reach a target sum.

dynamic programming combinatorics arrays counting

Write a function `count_target_sum_ways(nums, target)` that takes a list of integers `nums` (each `n_i > 0`) and an integer `target`, and returns the number of distinct ways to assign either a plus (+) or minus (-) sign to each number so that the signed sum equals exactly `target`.

Two assignments are considered different if at least one position receives a different sign. The order of numbers is fixed.

You may assume the answer fits within a 64-bit signed integer.

Constraints

0 <= len(nums) <= 20
1 <= nums[i] <= 1000
-10000 <= target <= 10000
Expected time complexity: O(n * S) where S is the sum of all nums (or O(2^n) for brute force, but DP is expected).

Example

>>> count_target_sum_ways([1, 1, 1, 1, 1], 3)
5
>>> count_target_sum_ways([1], 1)
1
>>> count_target_sum_ways([1], -1)
1
>>> count_target_sum_ways([], 0)
1
>>> count_target_sum_ways([], 5)
0

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of classic subset sum DP. Each number can be added or subtracted.

Let total = sum(nums). If (target + total) is odd or target > total, answer is 0.

The number of ways equals the number of subsets with sum (target + total)//2.

Use a 1D DP array over possible subset sums to avoid 2D memory.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.