Medium 0/1 Knapsack 2-D Dynamic Programming
In plain English: Assign a plus or minus sign to each number so they all add up to a target. Count the ways.
Reduce to subset sum: if P is the positive subset sum, then P - (total - P) = target, so P = (total + target) / 2. Now count subsets that sum to P using 0/1 knapsack DP.
Prompt
Given an integer array nums and a target, assign + or - to each number to make the sum equal to target. Return the number of ways.
Try to write it from scratch before scrolling down.
Solution
def find_target_sum_ways(nums, target):
total = sum(nums)
if (total + target) % 2 != 0 or abs(target) > total:
return 0
subset_sum = (total + target) // 2
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for j in range(subset_sum, num - 1, -1): # reverse for 0/1
dp[j] += dp[j - num]
return dp[subset_sum]
# Test: find_target_sum_ways([1,1,1,1,1], 3) == 5
# Test: find_target_sum_ways([1], 1) == 1