Target Sum

Med

#0481Time: O(2^n), where `n` is the length of the `nums` array. At each step, the function branches into two recursive calls, leading to a recursion tree with `2^n` leaf nodes.Space: O(n), where `n` is the length of the `nums` array. This space is used by the recursion call stack, which can go as deep as `n`.3 companies

Patterns

Dynamic Programming Backtracking

Data structures

Array

Companies

Myntra ServiceNow Pinterest

Prompt

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.

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 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

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses recursion to explore every possible combination of + and - signs for the numbers in the input array. It constructs a binary decision tree where, at each level corresponding to an element in nums, it branches into two possibilities: adding the element or subtracting it. The total count is the number of paths in this tree that result in the target sum.

Algorithm

Define a recursive function, say calculate(nums, index, currentSum, target).
The base case for the recursion is when index reaches the end of the nums array (index == nums.length).
- If currentSum is equal to target, it means we have found a valid expression. Return 1.
- Otherwise, return 0.
In the recursive step, for the number at nums[index], we explore both possibilities:
1. Adding the number: Make a recursive call calculate(nums, index + 1, currentSum + nums[index], target).
2. Subtracting the number: Make a recursive call calculate(nums, index + 1, currentSum - nums[index], target).
The total number of ways is the sum of the results from these two recursive calls.
The initial call to start the process is calculate(nums, 0, 0, target).

Walkthrough

The core idea is to build a recursive function that traverses through the nums array. This function keeps track of the current index being processed and the sum accumulated so far. For each number, the function calls itself twice: once for the case where the number is added to the sum, and once for the case where it's subtracted. The recursion stops when all numbers have been processed. At this point, if the accumulated sum equals the target, we have found one valid expression. The final result is the total count of all such valid expressions found across all recursive paths.

1class Solution {2    int count = 0;3    public int findTargetSumWays(int[] nums, int target) {4        calculate(nums, 0, 0, target);5        return count;6    }7    public void calculate(int[] nums, int i, int sum, int target) {8        if (i == nums.length) {9            if (sum == target) {10                count++;11            }12        } else {13            calculate(nums, i + 1, sum + nums[i], target);14            calculate(nums, i + 1, sum - nums[i], target);15        }16    }17}

Complexity

Time

O(2^n), where `n` is the length of the `nums` array. At each step, the function branches into two recursive calls, leading to a recursion tree with `2^n` leaf nodes.

Space

O(n), where `n` is the length of the `nums` array. This space is used by the recursion call stack, which can go as deep as `n`.

Trade-offs

Pros

Simple to conceptualize and implement.
Provides a clear, direct translation of the problem statement into code.

Cons

Extremely inefficient due to its exponential time complexity.
Leads to a 'Time Limit Exceeded' error on platforms like LeetCode for all but the smallest inputs.
Recalculates the same subproblems multiple times.

This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. It avoids re-computing results for the same subproblems by storing them in a cache (e.g., a 2D array or a hash map). A subproblem is uniquely identified by the current index in the nums array and the current accumulated sum.

Algorithm

The state of a subproblem can be defined by (index, currentSum).
Create a memoization table, memo[index][sum], to store the results of computed subproblems. A 2D array is suitable for this.
Since the sum can be negative, map it to a non-negative index using an offset. The total sum of all numbers in nums can be used as this offset.
The recursive function calculate(index, sum) first checks if the result for the state (index, sum) is already in the memoization table. If yes, it returns the stored value.
If not, it computes the result by making the two recursive calls (for adding and subtracting nums[index]) as in the brute-force approach.
Before returning, it stores the computed result in the memoization table for future use.

Walkthrough

The brute-force approach suffers from solving the same subproblems repeatedly. For example, reaching a sum of S at index i can happen through different paths, but the number of ways to reach the target from this state (i, S) is always the same. We can cache these results. We define a state by (index, sum). A 2D array memo[index][sum + offset] is used to store the number of ways to reach the target from the current index with the current sum. The offset is needed because the sum can be negative, and array indices must be non-negative. Before any recursive computation, we check our memo table. If a result exists, we use it directly. Otherwise, we compute it, store it, and then return it.

1import java.util.Arrays;2 3class Solution {4    public int findTargetSumWays(int[] nums, int target) {5        int totalSum = 0;6        for (int num : nums) {7            totalSum += num;8        }9        10        if (Math.abs(target) > totalSum) {11            return 0;12        }13        14        int[][] memo = new int[nums.length][2 * totalSum + 1];15        for (int[] row : memo) {16            Arrays.fill(row, Integer.MIN_VALUE);17        }18        19        return calculate(nums, 0, 0, target, memo, totalSum);20    }21    22    private int calculate(int[] nums, int i, int sum, int target, int[][] memo, int totalSum) {23        if (i == nums.length) {24            return sum == target ? 1 : 0;25        }26        27        if (memo[i][sum + totalSum] != Integer.MIN_VALUE) {28            return memo[i][sum + totalSum];29        }30        31        int add = calculate(nums, i + 1, sum + nums[i], target, memo, totalSum);32        int subtract = calculate(nums, i + 1, sum - nums[i], target, memo, totalSum);33        34        memo[i][sum + totalSum] = add + subtract;35        return memo[i][sum + totalSum];36    }37}

Complexity

Time

O(n * S), where `n` is the number of elements and `S` is the total sum. The number of unique states `(index, sum)` is `n * (2*S + 1)`, and each state is computed once.

Space

O(n * S), where `n` is the number of elements and `S` is the total sum of elements in `nums`. This space is dominated by the memoization table. The recursion stack adds an O(n) factor.

Trade-offs

Pros

Drastically improves performance over brute force by eliminating redundant computations.
Guarantees that each subproblem is solved only once.

Cons

Requires significant space for the memoization table, which can be large if the sum of numbers is high.
The logic for handling negative sums with an offset adds a layer of complexity.

This approach converts the top-down memoized recursion into a bottom-up iterative solution. It builds a 2D DP table to systematically compute the number of ways to form every possible sum using a growing subset of the input numbers, from the first element up to the last.

Algorithm

Create a 2D DP table, dp[i][j], where dp[i][j] stores the number of ways to achieve a sum j using the first i elements of nums.
Use an offset to handle negative sums. The table size will be (n+1) x (2*S+1), where n is the number of elements and S is their total sum. dp[i][sum + S] will store the result.
Initialize the table. The base case is dp[0][S] = 1, which means there is one way to get a sum of 0 with an empty set of numbers.
Iterate from i = 1 to n. For each element nums[i-1], iterate through all possible sums s.
The transition relation is: if dp[i-1][s] is greater than 0, it means sum s - S was achievable with i-1 elements. We can then contribute this count to two new sums with i elements: (s - S) + nums[i-1] and (s - S) - nums[i-1]. So, we update dp[i][s + nums[i-1]] and dp[i][s - nums[i-1]].
The final answer is dp[n][target + S].

Walkthrough

Instead of recursion, we can use a table to build up the solution iteratively. Let dp[i][j] be the number of ways to assign signs to the first i numbers in nums such that their sum is j. Again, since j can be negative, we use an offset. Let S be the sum of all numbers in nums. Our DP table will be dp[nums.length + 1][2 * S + 1], and dp[i][sum + S] will store the number of ways. We start with dp[0][S] = 1 (one way to get sum 0 with 0 numbers). Then, for each number num from nums, we iterate through the previous row of the DP table (dp[i-1]). For each sum s that had a non-zero count, we update the current row (dp[i]) by adding the count to dp[i][s + num] and dp[i][s - num]. After processing all numbers, the answer will be in dp[nums.length][target + S].

1class Solution {2    public int findTargetSumWays(int[] nums, int target) {3        int totalSum = 0;4        for (int num : nums) {5            totalSum += num;6        }7 8        if (Math.abs(target) > totalSum) {9            return 0;10        }11 12        int offset = totalSum;13        int[][] dp = new int[nums.length + 1][2 * totalSum + 1];14        dp[0][offset] = 1; // Base case15 16        for (int i = 1; i <= nums.length; i++) {17            int num = nums[i - 1];18            for (int s = 0; s < 2 * totalSum + 1; s++) {19                if (dp[i - 1][s] > 0) {20                    dp[i][s + num] += dp[i - 1][s];21                    dp[i][s - num] += dp[i - 1][s];22                }23            }24        }25 26        return dp[nums.length][target + offset];27    }28}

Complexity

Time

O(n * S). We iterate through `n` numbers, and for each, we iterate through a range of sums of size `2*S`.

Space

O(n * S), where `n` is the number of elements and `S` is their total sum. This is for the 2D DP table.

Trade-offs

Pros

Avoids recursion overhead, which can be slightly more efficient in practice than the memoized approach.
Systematic and easy to reason about the state transitions.

Cons

The space complexity is high, O(n * S), which can be a problem if the sum of numbers is large.

This highly efficient approach reformulates the problem into a classic 0/1 knapsack-style problem, specifically the "Subset Sum" problem. By using a bit of algebra, we can determine that the task is equivalent to finding the number of subsets of nums that sum to a specific value. This transformed problem can then be solved with a space-optimized 1D dynamic programming approach.

Algorithm

Calculate totalSum, the sum of all elements in nums.
The problem can be rephrased as finding a subset of nums, let's call it P, to which we assign + signs (the rest, N, get - signs). We need sum(P) - sum(N) = target.
We also know sum(P) + sum(N) = totalSum.
Adding these two equations yields 2 * sum(P) = target + totalSum, which simplifies to sum(P) = (target + totalSum) / 2.
The problem is now to find the number of subsets of nums that sum to subsetSum = (target + totalSum) / 2.
Check for edge cases: if target + totalSum is odd or negative, no solution is possible, so return 0.
Use a 1D DP array, dp, of size subsetSum + 1. dp[j] will store the number of ways to form sum j.
Initialize dp[0] = 1 (one way to make sum 0: with an empty set).
Iterate through each num in nums. For each num, update the dp array: dp[j] = dp[j] + dp[j - num] for j from subsetSum down to num.
The final answer is dp[subsetSum].

Walkthrough

Let the sum of numbers with a + sign be sum(P) and the sum of numbers with a - sign be sum(N). We are looking for sum(P) - sum(N) = target. We know that sum(P) + sum(N) = totalSum. By adding these two equations, we get 2 * sum(P) = target + totalSum, which means sum(P) = (target + totalSum) / 2. This transforms the problem into: find the number of subsets of nums that have a sum equal to (target + totalSum) / 2. This is a standard subset sum problem. We can solve it using a 1D DP array, dp, where dp[i] stores the number of subsets that sum to i. We iterate through each number in nums and update the dp array. The final answer is the value at dp[(target + totalSum) / 2].

1class Solution {2    public int findTargetSumWays(int[] nums, int target) {3        int totalSum = 0;4        for (int num : nums) {5            totalSum += num;6        }7 8        // If (target + totalSum) is odd or target is unreachable, no solution exists.9        if (Math.abs(target) > totalSum || (target + totalSum) % 2 != 0) {10            return 0;11        }12 13        int subsetSum = (target + totalSum) / 2;14        15        int[] dp = new int[subsetSum + 1];16        dp[0] = 1; // Base case: one way to make sum 0 (with an empty set)17 18        for (int num : nums) {19            // Iterate backwards to use each number at most once per subset20            for (int j = subsetSum; j >= num; j--) {21                dp[j] = dp[j] + dp[j - num];22            }23        }24 25        return dp[subsetSum];26    }27}

Complexity

Time

O(n * S), where `n` is the number of elements and `S` is the target subset sum. This is asymptotically the same as the other DP approaches but often faster in practice as the target subset sum is smaller than the full sum range.

Space

O(S), where `S` is the target subset sum, which is at most the total sum of `nums`. This is a significant improvement over the O(n * S) space of previous DP approaches.

Trade-offs

Pros

Most efficient in terms of space complexity.
The logic is clean, avoiding the need for negative index handling or offsets.
It's a classic and powerful DP pattern.

Cons

The mathematical transformation to the subset sum problem might not be immediately obvious.

Solutions

Solution

1class Solution {2public3  int findTargetSumWays(int[] nums, int target) {4    int s = 0;5    for (int v : nums) {6      s += v;7    }8    if (s < target || (s - target) % 2 != 0) {9      return 0;10    }11    int n = (s - target) / 2;12    int[] dp = new int[n + 1];13    dp[0] = 1;14    for (int v : nums) {15      for (int j = n; j >= v; --j) {16        dp[j] += dp[j - v];17      }18    }19    return dp[n];20  }21}

1/** * @param {number[]} nums * @param {number} target * @return {number} */ var findTargetSumWays =2  function (nums, target) {3    let s = 0;4    for (let v of nums) {5      s += v;6    }7    if (s < target || (s - target) % 2 != 0) {8      return 0;9    }10    const m = nums.length;11    const n = (s - target) / 2;12    let dp = new Array(n + 1).fill(0);13    dp[0] = 1;14    for (let i = 1; i <= m; ++i) {15      for (let j = n; j >= nums[i - 1]; --j) {16        dp[j] += dp[j - nums[i - 1]];17      }18    }19    return dp[n];20  };

1class Solution : def findTargetSumWays ( self , nums : List [ int ], target : int ) -> int : s = sum ( nums ) if s < target or ( s - target ) % 2 != 0 : return 0 n = ( s - target ) // 2 dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 for v in nums : for j in range ( n , v - 1 , - 1 ): dp [ j ] += dp [ j - v ] return dp [ - 1 ]

1class Solution { public: int findTargetSumWays ( vector < int >& nums , int target ) { int s = accumulate ( nums . begin (), nums . end (), 0 ); if ( s < target || ( s - target ) % 2 != 0 ) return 0 ; int n = ( s - target ) / 2 ; vector < int > dp ( n + 1 ); dp [ 0 ] = 1 ; for ( int & v : nums ) for ( int j = n ; j >= v ; -- j ) dp [ j ] += dp [ j - v ]; return dp [ n ]; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int findTargetSumWays(int[] nums, int target) {4    int s = 0;5    for (int v : nums) {6      s += v;7    }8    if (s < target || (s - target) % 2 != 0) {9      return 0;10    }11    int n = (s - target) / 2;12    int[] dp = new int[n + 1];13    dp[0] = 1;14    for (int v : nums) {15      for (int j = n; j >= v; --j) {16        dp[j] += dp[j - v];17      }18    }19    return dp[n];20  }21}

1/** * @param {number[]} nums * @param {number} target * @return {number} */ var findTargetSumWays =2  function (nums, target) {3    let s = 0;4    for (let v of nums) {5      s += v;6    }7    if (s < target || (s - target) % 2 != 0) {8      return 0;9    }10    const m = nums.length;11    const n = (s - target) / 2;12    let dp = new Array(n + 1).fill(0);13    dp[0] = 1;14    for (let i = 1; i <= m; ++i) {15      for (let j = n; j >= nums[i - 1]; --j) {16        dp[j] += dp[j - nums[i - 1]];17      }18    }19    return dp[n];20  };

1class Solution : def findTargetSumWays ( self , nums : List [ int ], target : int ) -> int : s = sum ( nums ) if s < target or ( s - target ) % 2 != 0 : return 0 n = ( s - target ) // 2 dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 for v in nums : for j in range ( n , v - 1 , - 1 ): dp [ j ] += dp [ j - v ] return dp [ - 1 ]

1class Solution { public: int findTargetSumWays ( vector < int >& nums , int target ) { int s = accumulate ( nums . begin (), nums . end (), 0 ); if ( s < target || ( s - target ) % 2 != 0 ) return 0 ; int n = ( s - target ) / 2 ; vector < int > dp ( n + 1 ); dp [ 0 ] = 1 ; for ( int & v : nums ) for ( int j = n ; j >= v ; -- j ) dp [ j ] += dp [ j - v ]; return dp [ n ]; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.