Target Sum with Positive and Negative Signs
Transform the target-sum assignment problem into a knapsack on subset-sum difference, solving it in O(n × sum) time.
The Target Sum Problem
Given an integer array nums and an integer target, assign a + or - sign to each number so that the resulting expression evaluates to target. Return the number of distinct ways to do this. For example, with nums=[1,1,1,1,1] and target=3, there are 5 ways (choose 4 elements to be positive, 1 to be negative in different positions).
Brute Force: DFS Enumeration
A DFS approach assigns each number either + or - and recurses, returning the count of leaf nodes that reach target. This is correct but has O(2^n) time complexity — exponential. For n=20 this is over one million recursive calls. The DFS approach is worth mentioning first, then quickly pivoting to the DP optimisation.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5All lessons in this course
- 0/1 Knapsack and Space Optimisation
- Unbounded Knapsack and Coin Change II
- Partition Equal Subset Sum
- Target Sum with Positive and Negative Signs