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.
Target Sum with Positive and Negative Signs is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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)) # 5Memoised DFS
Add memoisation to the DFS: the state is (index, current_sum). Since current_sum can range from -total to +total, there are O(n × total) unique states. With memoisation, the DFS runs in O(n × total) time and space. This works and is valid in interviews, but the transformation-based DP is more elegant and space-efficient.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Mathematical Transformation
Let P be the set of numbers assigned + and N the set assigned -. Then: sum(P) - sum(N) = target and sum(P) + sum(N) = total. Adding: 2 × sum(P) = target + total, so sum(P) = (target + total) / 2. The problem reduces to: count subsets of nums summing to (target + total) / 2. This is exactly the 'count subsets' variant of the 0/1 knapsack.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')Validity Checks Before DP
Before running the DP, check: (1) target + total must be even (otherwise sum(P) is not an integer — impossible); (2) abs(target) > total means the target is unachievable even if all signs align. If either check fails, return 0 immediately. These checks handle edge cases cleanly without special-casing inside the DP loop.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Tracing Through a Small Example
For nums=[1,1,1,1,1], target=3: total=5, new_target=(3+5)//2=4. We count subsets summing to 4 from [1,1,1,1,1]. This is C(5,4)=5 (choose 4 ones to be positive, the 5th is negative: 1+1+1+1-1=3). The DP correctly returns 5. The transformation elegantly maps the sign-assignment problem to a standard subset-count problem.
Handling Zeros in nums
If nums contains zeros, assigning + or - to a zero doesn't change the sum. Each zero doubles the number of valid assignments. The DP naturally handles this: when processing num=0, the inner loop range(new_target, -1, -1) runs from new_target down to 0, and dp[c] += dp[c - 0] = dp[c] doubles all reachable sums. No special handling needed if you use range(new_target, num-1, -1) which starts from new_target down to 0 when num=0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Complexity Comparison
The brute-force DFS is O(2^n). The memoised DFS is O(n × total) time and O(n × total) space. The transformation-based 1D DP is O(n × new_target) time and O(new_target) space, where new_target ≤ total. The 1D DP uses significantly less space than memoisation because it discards the index dimension through the transformation.
Connection to Other Knapsack Problems
Target Sum ties together multiple knapsack concepts: it starts as an assignment problem, transforms into subset sum (like Partition Equal Subset Sum), and uses the same 0/1 knapsack backward-iteration template but with counting (like Coin Change II). Mastering these connections lets you rapidly classify new problems in interviews by their structural similarity to known patterns.
Edge Cases and Interview Notes
Key cases: (1) target = total: only one way (all positive); (2) target = -total: only one way (all negative); (3) target = 0 with all zeros: answer is 2^n; (4) very large total but small n — the 1D DP array size is bounded by total/2. In interviews, walk through the transformation step verbally before coding — it is the non-obvious insight that separates strong candidates.
2D DP Alternative Without Transformation
Without the transformation, define dp[i][s] = number of ways to assign signs to first i numbers reaching sum s. The sum can be negative, so offset by total: use dp[i][s + total]. This requires a 2D table of size (n+1) × (2*total+1). While correct, it uses more space and is harder to code quickly under interview pressure than the 1D knapsack after transformation.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Target Sum transforms sign-assignment into counting subsets summing to (target + total) / 2, the 1D 0/1 knapsack backward-iteration counts subsets in O(n × new_target) time and O(new_target) space, and early validity checks (odd sum, |target| > total) prevent unnecessary DP execution. Next up we enter shortest-path territory with Dijkstra's algorithm and a priority queue.
Frequently asked questions
Is the “Target Sum with Positive and Negative Signs” lesson free?
Yes — the full text of “Target Sum with Positive and Negative Signs” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Target Sum with Positive and Negative Signs” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All 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