[Medium] 494. Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols + and - before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a + before 2 and a - before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Examples
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums equal to target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Thinking Process
- Mathematical Transformation: Convert to subset sum problem
- Define state: what subproblem does
dp[i](ordp[i][j]) represent? - Recurrence: how does the answer build from smaller indices?
- Base cases first; optimize space if only prior row/layer is needed.
Common Approaches
Typical techniques for this pattern:
| Approach | Time | Space | Notes |
|---|---|---|---|
| 1D DP (this problem) | O(n) | O(n) or O(1) | Linear recurrence |
| 2D DP | O(nm) | O(nm) or O(n) | Grid or two-sequence problems |
| State machine DP | O(n) | O(1) | Buy/sell, hold/not-hold states |
| Memoization (top-down) | Same as DP | O(n) | Recursive + cache |
Solution
Time Complexity: O(n × sum)
Space Complexity: O(sum)
Convert the problem to a subset sum problem using mathematical transformation.
class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
totalSum = sum(nums)
# invalid cases
if abs(target) > totalSum or (target + totalSum) % 2 != 0:
return 0
subsetSum = (target + totalSum) // 2
dp = [0] * (subsetSum + 1)
dp[0] = 1
for num in nums:
for i in range(subsetSum, num - 1, -1):
dp[i] += dp[i - num]
return dp[subsetSum]
Solution Explanation
Approach: 1D DP (this problem)
Key idea: 1. Mathematical Transformation: Convert to subset sum problem
How the code works:
- Mathematical Transformation: Convert to subset sum problem
- Define state: what subproblem does
dp[i](ordp[i][j]) represent? - Recurrence: how does the answer build from smaller indices?
- Base cases first; optimize space if only prior row/layer is needed.
- Define state: what subproblem does
Walkthrough — input nums = [1,1,1,1,1], target = 3, expected output 5:
There are 5 ways to assign symbols to make the sum of nums equal to target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
| Approach | Time Complexity | Space Complexity | |———-|—————-|——————| | Brute Force | O(2^n) | O(n) | | Memoization | O(n × sum) | O(n × sum) | | DP (Subset Sum) | O(n × sum) | O(sum) |
Algorithm Breakdown
1. Validation Check
if (target + totalSum) % 2 != 0 or abs(target) > totalSum:
return 0
Why this check?
- If
(target + totalSum)is odd,subsetSumwould be fractional (impossible) - If
abs(target) > totalSum, it’s impossible to achieve the target
2. Subset Sum Calculation
subsetSum = (target + totalSum) / 2
Mathematical proof:
S+ - S- = target(equation 1)S+ + S- = totalSum(equation 2)- Adding equations:
2S+ = target + totalSum - Therefore:
S+ = (target + totalSum) / 2
3. DP Array Initialization
list[int] dp(subsetSum + 1, 0)
dp[0] = 1 # One way to make sum 0 (empty subset)
4. Bottom-Up DP
for num in nums:
for i in range(subsetSum, num - 1, -1):
dp[i] += dp[i - num]
Why iterate backwards?
- Prevents using the same number twice in one iteration
- Ensures we only use numbers from previous iterations
Complexity
| Approach | Time Complexity | Space Complexity | |———-|—————-|——————| | Brute Force | O(2^n) | O(n) | | Memoization | O(n × sum) | O(n × sum) | | DP (Subset Sum) | O(n × sum) | O(sum) |
Common Mistakes
- Impossible target:
nums = [1], target = 2→0 - Single element:
nums = [1], target = 1→1 - Zero target:
nums = [1,1], target = 0→2 -
Large numbers:
nums = [1000], target = 1000→1 - Forgetting validation: Not checking if target is achievable
- Wrong iteration order: Using forward iteration in DP
- Incorrect subset sum formula: Wrong calculation of
subsetSum - Array bounds: Not handling edge cases properly
Related Problems
Why This Solution is Optimal
- Mathematical Insight: Transforms exponential problem to polynomial
- Space Efficient: Uses 1D DP array instead of 2D
- Early Termination: Validates feasibility before computation
- Optimal Complexity: O(n × sum) is the best possible for this problem
References
- LC 494: Target Sum on LeetCode
- LeetCode Discuss — LC 494: Target Sum
- LeetCode Editorial (may require premium)
Key Takeaways
- Mathematical Transformation: Convert to subset sum problem
- DP Optimization: Use 1D array instead of 2D
- Backward Iteration: Prevents double counting
- Early Validation: Check feasibility before computation