#494

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Target Sum

Target Sum requires counting all expressions from nums using '+' or '-' that evaluate exactly to the given target integer value.

array dynamic programming backtracking

Problem Statement

Given an integer array nums and an integer target, you must assign a '+' or '-' before each element to form an expression. Your goal is to count how many distinct expressions evaluate exactly to target.

Return the total number of different expressions that can be built from nums using '+' and '-' symbols so that the sum of all elements matches the target value. Arrays can include zeros, which affect multiple valid expressions.

Examples

Example 1

Input: nums = [1,1,1,1,1], target = 3

Output: 5

There are 5 ways to assign symbols to make the sum of nums be 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

Example details omitted.

Constraints

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Solution Approach

Recursive Backtracking

Start from the first index and recursively choose '+' or '-' for each number, accumulating the current sum. Count paths where the accumulated sum equals the target at the end. This approach demonstrates the combinatorial explosion and highlights why memoization or DP is needed.

Dynamic Programming via State Transition

Define dp[i][sum] as the number of ways to reach sum using the first i numbers. Transition using dp[i][sum + nums[i]] and dp[i][sum - nums[i]] for each element. Initialize dp[0][0] = 1 and iterate through nums. This reduces repeated calculation and efficiently tracks all possible sums.

Subset Sum Transformation

Transform the problem into a subset sum by solving for sum(P) - sum(N) = target, where P and N are positive and negative subsets. Use DP to count subsets with sum = (target + totalSum)/2. This reduces state space and clarifies edge handling like unreachable targets or zero elements.

Complexity Analysis

Metric	Value
Time	O(n \cdot \text{totalSum})
Space	O(2 \cdot \text{totalSum}) \approx O(\text{totalSum})

Time complexity is O(n \cdot totalSum) since each number updates sums in DP. Space complexity is O(totalSum) because only two layers of DP are needed for state transitions.

What Interviewers Usually Probe

Check if candidates recognize the combinatorial nature and naive exponential backtracking.
Notice whether they optimize using memoization or DP for cumulative sum tracking.
Observe handling of zeros and negative targets in expressions.

Common Pitfalls or Variants

Common pitfalls

Failing to handle zeros correctly, which can double-count certain expressions if not treated in DP.
Ignoring negative cumulative sums in DP, causing index errors or missed combinations.
Attempting pure backtracking without memoization, leading to timeouts for arrays near length 20.

Follow-up variants

Count expressions using only '+' signs that reach half the total sum of nums.
Modify the problem to allow multiplication or division signs with similar state tracking.
Return all valid expressions as strings instead of just the count, emphasizing backtracking construction.

FAQ

What is the optimal approach to solve Target Sum efficiently?

The most efficient approach uses state transition dynamic programming, tracking cumulative sums and reducing redundant recursive calls.

Can backtracking alone handle large input arrays?

Backtracking alone is exponential and may time out for arrays near length 20, so DP or memoization is recommended.

How does the presence of zeros in nums affect the solution?

Zeros double the number of valid expressions at their positions, so DP must account for this to avoid undercounting.

Is there a way to convert Target Sum into a subset sum problem?

Yes, by representing the problem as sum(P) - sum(N) = target, you can compute valid subsets whose sum equals (target + totalSum)/2.

What are common mistakes when implementing DP for Target Sum?

Common mistakes include mismanaging negative sums in the DP array, not initializing the base case correctly, and double-counting zeros.

terminal

Solution

Solution 1: Dynamic Programming

Let's denote the sum of all elements in the array $\textit{nums}$ as $s$, and the sum of elements to which we assign a negative sign as $x$. Therefore, the sum of elements with a positive sign is $s - x$. We have:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target or (s - target) % 2:
            return 0
        m, n = len(nums), (s - target) // 2
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i - 1][j - x]
        return f[m][n]

Solution 2: Dynamic Programming (Space Optimization)

We can observe that in the state transition equation of Solution 1, the value of $f[i][j]$ is only related to $f[i - 1][j]$ and $f[i - 1][j - \textit{nums}[i - 1]]$. Therefore, we can eliminate the first dimension of the space and use only a one-dimensional array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target or (s - target) % 2:
            return 0
        m, n = len(nums), (s - target) // 2
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i - 1][j - x]
        return f[m][n]

Continue Practicing

#473 matchsticks to square #526 beautiful arrangement #638 shopping offers