494. Target Sum - Explanation

Description

You are given an array of integers nums and an integer target.

For each number in the array, you can choose to either add or subtract it to a total sum.

For example, if nums = [1, 2], one possible sum would be "+1-2=-1".

If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: "+1-1" and "-1+1".

Return the number of different ways that you can build the expression such that the total sum equals target.

Example 1:

Input: nums = [2,2,2], target = 2

Output: 3

Explanation: There are 3 different ways to sum the input numbers to get a sum of 2.
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2

Constraints:

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

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * m) time and O(n * m) space, where n is the size of the input array and m is the sum of all the elements in the array.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each recursion step: assigning a positive or negative sign.

Hint 2

We recursively iterate through the array using index i, tracking the current sum along the recursive path. Each step branches into two paths, and we sum the number of ways to reach the target. If the index i goes out of bounds, we return 1 if the current sum equals the target; otherwise, we return 0.

Hint 3

This approach is exponential. We can use memoization to cache recursive call results and avoid redundant calculations. A hash map or a 2D array with modifications can be used for caching. If using a 2D array, the dimensions can be (n * (2m + 1)), where n is the array size and m represents the sum of the array elements.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

This problem asks us to count how many different ways we can assign a + or - sign to each number so that the final sum equals the target.

At every index, we have two independent choices:

add the current number to the total
subtract the current number from the total

Using recursion, we try all possible sign assignments.
The recursive function represents:
"How many ways can we reach the target starting from index i with the current sum total?"

When all numbers are processed, we simply check whether the accumulated sum equals the target.

Algorithm

Define a recursive function backtrack(i, total):
- i is the current index in the array
- total is the sum formed so far
If i reaches the end of the array:
- Return 1 if total equals the target
- Otherwise, return 0
For the current index:
- Recurse by adding the current number to total
- Recurse by subtracting the current number from total
Add the results of both recursive calls
Start the recursion from index 0 with an initial sum of 0
Return the final count of valid ways

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        def backtrack(i, total):
            if i ==len(nums):
                return  total == target

            return (backtrack(i + 1, total + nums[i]) +
                    backtrack(i + 1, total - nums[i]))

        return backtrack(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

This problem asks us to count the number of ways to assign a + or - sign to each number so that the final sum equals the target.

The recursive solution tries all possible sign combinations, but many subproblems repeat. To avoid recomputing the same states, we use top-down dynamic programming (memoization).

Each state is uniquely defined by:

the current index i
the current accumulated sum total

The recursive function answers the question:
"How many ways can we reach the target starting from index i with the current sum total?"

By caching results for each state, we significantly improve efficiency.

Algorithm

Create a memoization map dp where:
- the key is (i, total)
- the value is the number of ways to reach the target from that state
Define a recursive function backtrack(i, total):
- i represents the current index in the array
- total represents the sum formed so far
If i reaches the end of the array:
- Return 1 if total equals the target
- Otherwise, return 0
If the current state (i, total) is already in dp:
- Return the stored value to avoid recomputation
Compute the result by exploring both choices:
- Add the current number to total
- Subtract the current number from total
Store the computed result in dp[(i, total)]
Start the recursion from index 0 with an initial sum of 0
Return the final result

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {}  # (index, total) -> # of ways

        def backtrack(i, total):
            if i == len(nums):
                return 1 if total == target else 0
            if (i, total) in dp:
                return dp[(i, total)]

            dp[(i, total)] = (backtrack(i + 1, total + nums[i]) +
                              backtrack(i + 1, total - nums[i]))
            return dp[(i, total)]

        return backtrack(0, 0)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the array $nums$ and $m$ is the sum of all the elements in the array.

3. Dynamic Programming (Bottom-Up)

Intuition

We need to count how many ways we can assign a + or - sign to each number so that the final sum equals the target.

Instead of using recursion, we can solve this using bottom-up dynamic programming, where we build solutions step by step as we process each number.

At each position, we keep track of:

all possible sums we can form
how many ways each sum can be formed

As we move forward, each existing sum can branch into two new sums by adding or subtracting the current number.

Algorithm

Let n be the length of the input array.
Create a list of maps dp of size n + 1:
- dp[i] stores how many ways each sum can be formed using the first i numbers
Initialize the base case:
- dp[0][0] = 1 since there is exactly one way to form sum 0 using no numbers
Iterate through the numbers from index 0 to n - 1:
For each existing (sum, count) in dp[i]:
- Add the current number → update dp[i + 1][sum + nums[i]]
- Subtract the current number → update dp[i + 1][sum - nums[i]]
After processing all numbers, dp[n][target] gives the number of valid ways
Return dp[n][target]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(n):
            for total, count in dp[i].items():
                dp[i + 1][total + nums[i]] += count
                dp[i + 1][total - nums[i]] += count

        return dp[n][target]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the array $nums$ and $m$ is the sum of all the elements in the array.

4. Dynamic Programming (Space Optimized)

Intuition

We want to count the number of ways to assign + and - signs to the numbers so that their final sum equals the target.

In the bottom-up DP approach, we used a separate data structure for each index. However, at each step, the new states depend only on the previous step, not on all earlier steps.

This means we can reuse a single data structure to keep track of all possible sums and how many ways each sum can be formed, updating it as we process each number.

Algorithm

Create a map dp where:
- the key represents a possible sum
- the value represents the number of ways to form that sum
Initialize dp[0] = 1 since there is exactly one way to reach sum 0 before using any numbers
For each number in the array:
- Create a new map next_dp to store updated sums
For every (total, count) in dp:
- Add the current number → update next_dp[total + num]
- Subtract the current number → update next_dp[total - num]
Replace dp with next_dp after processing the current number
After all numbers are processed, dp[target] gives the number of valid ways
Return dp[target]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = defaultdict(int)
        dp[0] = 1

        for num in nums:
            next_dp = defaultdict(int)
            for total, count in dp.items():
                next_dp[total + num] += count
                next_dp[total - num] += count
            dp = next_dp

        return dp[target]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(m)$

Where $n$ is the length of the array $nums$ and $m$ is the sum of all the elements in the array.