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

Topics

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.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion / Backtracking - Exploring all possible combinations by making choices at each step
Dynamic Programming (Memoization) - Caching results of subproblems defined by index and running sum
Dynamic Programming (Tabulation) - Building solutions bottom-up using hash maps to track reachable sums

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)

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return backtrack(0, 0, nums, target);
    }

    private int backtrack(int i, int total, int[] nums, int target) {
        if (i == nums.length) {
            return total == target ? 1 : 0;
        }
        return backtrack(i + 1, total + nums[i], nums, target) +
               backtrack(i + 1, total - nums[i], nums, target);
    }
}

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return backtrack(0, 0, nums, target);
    }

    int backtrack(int i, int total, vector<int>& nums, int target) {
        if (i == nums.size()) {
            return total == target;
        }
        return backtrack(i + 1, total + nums[i], nums, target) +
               backtrack(i + 1, total - nums[i], nums, target);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    findTargetSumWays(nums, target) {
        const backtrack = (i, total) => {
            if (i === nums.length) {
                return total === target ? 1 : 0;
            }
            return (
                backtrack(i + 1, total + nums[i]) +
                backtrack(i + 1, total - nums[i])
            );
        };

        return backtrack(0, 0);
    }
}

public class Solution {
    public int FindTargetSumWays(int[] nums, int target) {
        return Backtrack(0, 0, nums, target);
    }

    private int Backtrack(int i, int total, int[] nums, int target) {
        if (i == nums.Length) {
            return total == target ? 1 : 0;
        }
        return Backtrack(i + 1, total + nums[i], nums, target) +
               Backtrack(i + 1, total - nums[i], nums, target);
    }
}

func findTargetSumWays(nums []int, target int) int {
    var backtrack func(i int, total int) int
    backtrack = func(i int, total int) int {
        if i == len(nums) {
            if total == target {
                return 1
            }
            return 0
        }
        return backtrack(i+1, total+nums[i]) + backtrack(i+1, total-nums[i])
    }

    return backtrack(0, 0)
}

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        fun backtrack(i: Int, total: Int): Int {
            if (i == nums.size) {
                return if (total == target) 1 else 0
            }
            return backtrack(i + 1, total + nums[i]) +
                   backtrack(i + 1, total - nums[i])
        }

        return backtrack(0, 0)
    }
}

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        func backtrack(_ i: Int, _ total: Int) -> Int {
            if i == nums.count {
                return total == target ? 1 : 0
            }
            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)

public class Solution {
    private int[][] dp;
    private int totalSum;

    public int findTargetSumWays(int[] nums, int target) {
        totalSum = 0;
        for (int num : nums) totalSum += num;
        dp = new int[nums.length][2 * totalSum + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < 2 * totalSum + 1; j++) {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }
        return backtrack(0, 0, nums, target);
    }

    private int backtrack(int i, int total, int[] nums, int target) {
        if (i == nums.length) {
            return total == target ? 1 : 0;
        }
        if (dp[i][total + totalSum] != Integer.MIN_VALUE) {
            return dp[i][total + totalSum];
        }
        dp[i][total + totalSum] = backtrack(i + 1, total + nums[i], nums, target) +
                                  backtrack(i + 1, total - nums[i], nums, target);
        return dp[i][total + totalSum];
    }
}

class Solution {
    vector<vector<int>> dp;
    int totalSum;

public:
    int findTargetSumWays(vector<int>& nums, int target) {
        totalSum = accumulate(nums.begin(), nums.end(), 0);
        dp = vector<vector<int>>(nums.size(), vector<int>(2 * totalSum + 1, INT_MIN));
        return backtrack(0, 0, nums, target);
    }

    int backtrack(int i, int total, vector<int>& nums, int target) {
        if (i == nums.size()) {
            return total == target;
        }
        if (dp[i][total + totalSum] != INT_MIN) {
            return dp[i][total + totalSum];
        }
        dp[i][total + totalSum] = backtrack(i + 1, total + nums[i], nums, target) +
                                  backtrack(i + 1, total - nums[i], nums, target);
        return dp[i][total + totalSum];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    findTargetSumWays(nums, target) {
        const NEG_INF = Number.MIN_SAFE_INTEGER;
        const totalSum = nums.reduce((a, b) => a + b, 0);
        const dp = Array.from({ length: nums.length }, () =>
            Array(2 * totalSum + 1).fill(NEG_INF),
        );

        const backtrack = (i, total) => {
            if (i === nums.length) {
                return total === target ? 1 : 0;
            }
            if (dp[i][total + totalSum] !== NEG_INF) {
                return dp[i][total + totalSum];
            }
            dp[i][total + totalSum] =
                backtrack(i + 1, total + nums[i]) +
                backtrack(i + 1, total - nums[i]);
            return dp[i][total + totalSum];
        };

        return backtrack(0, 0);
    }
}

public class Solution {
    private int[,] dp;
    private int totalSum;

    public int FindTargetSumWays(int[] nums, int target) {
        totalSum = 0;
        foreach (var num in nums) totalSum += num;
        dp = new int[nums.Length, 2 * totalSum + 1];
        for (int i = 0; i < nums.Length; i++) {
            for (int j = 0; j < 2 * totalSum + 1; j++) {
                dp[i, j] = int.MinValue;
            }
        }
        return Backtrack(0, 0, nums, target);
    }

    private int Backtrack(int i, int total, int[] nums, int target) {
        if (i == nums.Length) {
            return total == target ? 1 : 0;
        }

        if (dp[i, total + totalSum] != int.MinValue) {
            return dp[i, total + totalSum];
        }

        dp[i, total + totalSum] = Backtrack(i + 1, total + nums[i], nums, target) +
                                  Backtrack(i + 1, total - nums[i], nums, target);
        return dp[i, total + totalSum];
    }
}

func findTargetSumWays(nums []int, target int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }

    dp := make([][]int, len(nums))
    for i := range dp {
        dp[i] = make([]int, 2*totalSum+1)
        for j := range dp[i] {
            dp[i][j] = math.MinInt32
        }
    }

    var backtrack func(i, total int) int
    backtrack = func(i, total int) int {
        if i == len(nums) {
            if total == target {
                return 1
            }
            return 0
        }

        if dp[i][total+totalSum] != math.MinInt32 {
            return dp[i][total+totalSum]
        }

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

    return backtrack(0, 0)
}

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        var totalSum = nums.sum()
        var dp = Array(nums.size) { IntArray(2 * totalSum + 1) { Int.MIN_VALUE } }

        fun backtrack(i: Int, total: Int): Int {
            if (i == nums.size) {
                return if (total == target) 1 else 0
            }
            if (dp[i][total + totalSum] != Int.MIN_VALUE) {
                return dp[i][total + totalSum]
            }
            dp[i][total + totalSum] = backtrack(i + 1, total + nums[i]) +
                                      backtrack(i + 1, total - nums[i])
            return dp[i][total + totalSum]
        }

        return backtrack(0, 0)
    }
}

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        let totalSum = nums.reduce(0, +)
        var dp = Array(repeating: Array(repeating: Int.min, count: 2 * totalSum + 1), count: nums.count)

        func backtrack(_ i: Int, _ total: Int) -> Int {
            if i == nums.count {
                return total == target ? 1 : 0
            }
            if dp[i][total + totalSum] != Int.min {
                return dp[i][total + totalSum]
            }
            dp[i][total + totalSum] = backtrack(i + 1, total + nums[i]) +
                                      backtrack(i + 1, total - nums[i])
            return dp[i][total + totalSum]
        }

        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]

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new HashMap<>();
        }
        dp[0].put(0, 1);

        for (int i = 0; i < n; i++) {
            for (Map.Entry<Integer, Integer> entry : dp[i].entrySet()) {
                int total = entry.getKey();
                int count = entry.getValue();
                dp[i + 1].put(total + nums[i],
                          dp[i + 1].getOrDefault(total + nums[i], 0) + count);
                dp[i + 1].put(total - nums[i],
                          dp[i + 1].getOrDefault(total - nums[i], 0) + count);
            }
        }
        return dp[n].getOrDefault(target, 0);
    }
}

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n + 1);
        dp[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (auto &p : dp[i]) {
                dp[i + 1][p.first + nums[i]] += p.second;
                dp[i + 1][p.first - nums[i]] += p.second;
            }
        }
        return dp[n][target];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    findTargetSumWays(nums, target) {
        const n = nums.length;
        let dp = Array.from({ length: n + 1 }, () => ({}));
        dp[0][0] = 1;

        for (let i = 0; i < n; i++) {
            for (let total in dp[i]) {
                total = Number(total);
                let count = dp[i][total];
                dp[i + 1][total + nums[i]] =
                    (dp[i + 1][total + nums[i]] || 0) + count;
                dp[i + 1][total - nums[i]] =
                    (dp[i + 1][total - nums[i]] || 0) + count;
            }
        }
        return dp[n][target] || 0;
    }
}

public class Solution {
    public int FindTargetSumWays(int[] nums, int S) {
        int n = nums.Length;
        Dictionary<int, int>[] dp = new Dictionary<int, int>[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new Dictionary<int, int>();
        }
        dp[0][0] = 1;

        for (int i = 0; i < n; i++) {
            foreach (var entry in dp[i]) {
                int total = entry.Key;
                int count = entry.Value;
                if (!dp[i + 1].ContainsKey(total + nums[i])) {
                    dp[i + 1][total + nums[i]] = 0;
                }
                dp[i + 1][total + nums[i]] += count;

                if (!dp[i + 1].ContainsKey(total - nums[i])) {
                    dp[i + 1][total - nums[i]] = 0;
                }
                dp[i + 1][total - nums[i]] += count;
            }
        }
        return dp[n].ContainsKey(S) ? dp[n][S] : 0;
    }
}

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        val n = nums.size
        val dp = Array(n + 1) { mutableMapOf<Int, Int>() }

        dp[0][0] = 1

        for (i in 0 until n) {
            for ((total, count) in dp[i]) {
                dp[i + 1][total + nums[i]] = dp[i + 1].getOrDefault(total + nums[i], 0) + count
                dp[i + 1][total - nums[i]] = dp[i + 1].getOrDefault(total - nums[i], 0) + count
            }
        }

        return dp[n][target] ?: 0
    }
}

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        let n = nums.count
        var dp = Array(repeating: [Int: Int](), count: n + 1)
        dp[0][0] = 1

        for i in 0..<n {
            for (total, count) in dp[i] {
                dp[i + 1][total + nums[i], default: 0] += count
                dp[i + 1][total - nums[i], default: 0] += count
            }
        }
        return dp[n][target, default: 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.

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]

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 1);

        for (int num : nums) {
            Map<Integer, Integer> nextDp = new HashMap<>();
            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
                int total = entry.getKey();
                int count = entry.getValue();
                nextDp.put(total + num,
                           nextDp.getOrDefault(total + num, 0) + count);
                nextDp.put(total - num,
                           nextDp.getOrDefault(total - num, 0) + count);
            }
            dp = nextDp;
        }
        return dp.getOrDefault(target, 0);
    }
}

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 1;

        for (int num : nums) {
            unordered_map<int, int> nextDp;
            for (auto& entry : dp) {
                int total = entry.first;
                int count = entry.second;
                nextDp[total + num] += count;
                nextDp[total - num] += count;
            }
            dp = nextDp;
        }
        return dp[target];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    findTargetSumWays(nums, target) {
        let dp = new Map();
        dp.set(0, 1);

        for (let num of nums) {
            let nextDp = new Map();
            for (let [total, count] of dp) {
                nextDp.set(total + num, (nextDp.get(total + num) || 0) + count);
                nextDp.set(total - num, (nextDp.get(total - num) || 0) + count);
            }
            dp = nextDp;
        }
        return dp.get(target) || 0;
    }
}

public class Solution {
    public int FindTargetSumWays(int[] nums, int target) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        dp[0] = 1;

        foreach (int num in nums) {
            Dictionary<int, int> nextDp = new Dictionary<int, int>();
            foreach (var entry in dp) {
                int total = entry.Key;
                int count = entry.Value;

                if (!nextDp.ContainsKey(total + num)) {
                    nextDp[total + num] = 0;
                }
                nextDp[total + num] += count;

                if (!nextDp.ContainsKey(total - num)) {
                    nextDp[total - num] = 0;
                }
                nextDp[total - num] += count;
            }
            dp = nextDp;
        }
        return dp.ContainsKey(target) ? dp[target] : 0;
    }
}

func findTargetSumWays(nums []int, target int) int {
    dp := make(map[int]int)
    dp[0] = 1

    for _, num := range nums {
        nextDp := make(map[int]int)
        for total, count := range dp {
            nextDp[total+num] += count
            nextDp[total-num] += count
        }
        dp = nextDp
    }

    return dp[target]
}

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        val dp = mutableMapOf(0 to 1)

        for (num in nums) {
            val nextDp = mutableMapOf<Int, Int>()
            for ((total, count) in dp) {
                nextDp[total + num] = nextDp.getOrDefault(total + num, 0) + count
                nextDp[total - num] = nextDp.getOrDefault(total - num, 0) + count
            }
            dp.clear()
            dp.putAll(nextDp)
        }

        return dp[target] ?: 0
    }
}

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        var dp = [0: 1]

        for num in nums {
            var nextDp = [Int: Int]()
            for (total, count) in dp {
                nextDp[total + num, default: 0] += count
                nextDp[total - num, default: 0] += count
            }
            dp = nextDp
        }
        return dp[target, default: 0]
    }
}

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.

Common Pitfalls

Incorrect Memoization Key

When using top-down DP, the state must include both the current index and the running sum. Forgetting to include one of these in the memoization key will cause incorrect caching and wrong results. The key should be (index, total) not just index or just total.

Not Handling Negative Sums in Array-Based DP

When using an array instead of a hashmap for memoization, the running sum can become negative. You must offset the sum by the total sum of all elements to convert it to a valid non-negative index. For example, use dp[i][total + totalSum] where totalSum is the sum of all numbers.

Modifying Map While Iterating (Space-Optimized DP)

In the space-optimized bottom-up approach, you cannot update dp while iterating over it. You must create a new map next_dp for the next state and then replace dp with next_dp after processing each number. Modifying dp in place leads to using updated values in the same iteration.