keetcoder

# 494. Target Sum

LeetCode Problem Link (opens new window)

Difficulty: Medium

You are given a list of non-negative integers, a1, a2, ..., an, and a target integer S. Now you have two symbols + and -. For each integer, you may choose either + or - as its prefix symbol in front of the integer.

Return the number of ways to assign symbols to make the sum of integers equal to the target S.

Example:

  • Input: nums: [1, 1, 1, 1, 1], S: 3
  • Output: 5

Explanation:

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

There are 5 ways to assign symbols to make the sum of the integers equal to 3.

Constraints:

  • The array is non-empty and has at most 20 elements.
  • The sum of the initial array will not exceed 1000.
  • The final result will be within the range of a 32-bit integer.

# Approach

If you're unfamiliar with the knapsack problem, it's best to first look at these two articles:

If you have studied the Backtracking Summary (opens new window) with "KeetCoder," instances of seeing this problem might give a subconscious indication that it can be brute-forced via backtracking.

In fact, it can be, and I'll provide corresponding code, although it exceeds time limits.

At first glance, this problem doesn't seem to relate to dynamic programming or knapsack-based approaches.

This problem requires finding a way to make the expression result in target. In doing so, it implies left combination - right combination = target.

left + right = sum, which is fixed. Hence, right = sum - left.

So, left - (sum - left) = target results in left = (target + sum)/2.

target is fixed, sum is fixed, so left can be determined.

Now the problem reduces to finding combinations in nums that sum to left.

# Backtracking Algorithm

In the Backtracking Summary (opens new window), if you've studied the problem — 0039.Combination Sum (opens new window) — you might find this problem familiar. It's a typical combination sum problem.

The code for the combination sum backtracking can largely be reused here with minimal modifications.

Alternatively, you can transform this into a sequence interval selection of + or - using backtracking, resulting in another approach.

Here’s the backtracking solution transformed into a combination sum problem:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (S > sum) return 0;
        if ((S + sum) % 2) return 0;
        int bagSize = (S + sum) / 2;

        result.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

The above code exceeds time limits.

Using memoized backtracking is possible, but let's focus on dynamic programming.

# Dynamic Programming (2D dp array)

Assuming that the sum of additions is x, the subtraction corresponds to sum - x.

Therefore, the relationship is: x - (sum - x) = target

That is, x = (target + sum) / 2.

The task then becomes: find all combinations of numbers from nums that sum to x, representing the knapsack capacity.

Here, x is the bagSize, which is the knapsack capacity we wish to determine.

Some of you might worry about the floor division when computing (target + sum) / 2.

To alleviate this, for instance, if sum equals 5 and target equals 2, it becomes unsolvable. Therefore:

if ((target + sum) % 2 == 1) return 0;
1

Additionally, if the absolute value of target exceeds sum, it’s also unsolvable.

if (abs(target) > sum) return 0;
1

Since each element is used once, this isn't like previous knapsack problems where the aim is to fill the knapsack maximally.

Here, the aim is how many ways the knapsack can be filled. Essentially, it's a combination problem.

# 1. Define dp array and index meaning

Using a 2D dp array first, let's solve the problem. dp[i][j] signifies using elements from index [0, i] to fill a knapsack of size j (including j), resulting in dp[i][j] many combinations.

For 01 knapsack definition, refer to Knapsack Theory 01 Knapsack-1 (opens new window) for defining dp array semantics.

# 2. Determine the recursive formula

Let's manually derive this 2D array.

Only consider item 0:

Filling a knapsack capacity of 0 has one combination, i.e., place 0 items.

Filling a knapsack capacity of 1 has one combination, i.e., place item 0.

Filling a knapsack capacity of 2 is not feasible, currently.

Consider item 0 and item 1:

Filling a knapsack capacity of 0 has one combination, i.e., place 0 items.

Filling a knapsack capacity of 1 has two combinations, i.e., place either item 0 or item 1.

Filling a knapsack capacity of 2 has one combination: place both item 0 and item 1.

Consider item 0, item 1, and item 2:

Filling a knapsack capacity of 0 has one combination, i.e., place 0 items.

Filling a knapsack capacity of 1 has three combinations: either place item 0, item 1, or item 2.

Filling a capacity of 2 has three, and of 3 has one.

Through this, deduce the directions for deriving dp[2][2].

For dp[2][2], how many directions lead to achieving capacity 2, three ways show how, outlined throughout.

If not placing item i: Capacity j excluding item i, with dp[i - 1][j] combinations.

If placing item i: Reduce the capacity for i, then the capacity j - item and find dp[i - 1][j - nums[i]] ways.

Here's a recap of the recursive formula:

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
1
2

# 3. Initialize dp array

Determine recursive direction first, derive from the top and to the sides.

So the top-left corner must be initialized. Initialization helps calculation, e.g., mark top rows and columns as 1 in dp array.

Therefore setup as follows:

int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) numZero++;
    dp[i][0] = (int) pow(2.0, numZero);
}
1
2
3
4
5

# 4. Determine traversal order

Identify the recursive sequence, for dp[2][2] dependency.

Transiting sideways implies filling left cell first, completing traversal.

Either vertically or horizontally is possible.

Here's the complete 2D dp approach using C++ code:

class Solution {
public:     
    int findTargetSumWays(vector<int>& nums, int target) {         
        int sum = 0;         
        for (int i = 0; i < nums.size(); i++) sum += nums[i];         
        if (abs(target) > sum) return 0;
        if ((target + sum) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;
        vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));
        dp[0][nums[0]] = 1;
        dp[0][0] = 1;
        int numZero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) numZero++;
            dp[i][0] = (int) pow(2.0, numZero);
        }

        for (int i = 1; i < nums.size(); i++) { 
            for (int j = 0; j <= bagSize; j++) { 
                if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
                else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
            }
        }
        return dp[nums.size() - 1][bagSize];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Dynamic Programming (1D dp array)

Derive 2D dp compression with 1D dp arrays; an overlay of rows makes reducing array dimensions possible.

Consequently reducing dimensions to make it one row and calculate from previous values.

# 2. Determine recursive formula

From the 2D dp formula: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

Dimensional reduction yields dp[j] = dp[j] + dp[j - nums[i]], equivalent to dp[j] += dp[j - nums[i]]

This will appear during permutation and combination solutions in knapsack!

# 3. Initialize dp array

Set dp[0] = 1 since packing a 0 full knapsack counts as 1 way, by placing 0 items.

# 4. Determine traversal order

Following insights from the 01 knapsack theory, maintain variability iterating in backward fashion to avoid duplicating element use.

# 5. Example to derive dp array

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

bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

The dp array state evolves:

Compare to the 2D dp array results ensured via the same approach.

Corresponding 1D DP C++ solution:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(target) > sum) return 0;
        if ((target + sum) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • Time Complexity: O(n × m), where n is the number of positives and m is the knapsack capacity
  • Space Complexity: O(m), where m is the knapsack capacity

# Expansion

Interpret the one-dimensional dp array recursive formula from the following perspective. (It remains easier analyzing from 2D DP arrays to 1D!)

  1. Calculate the recursive formula

Which ways to compute dp[j]?

Consider capturing each element nums[i] to result in ways summing of dp[j].

For example: for dp[j], where j is 5,

  • Putting one 1 (i.e., nums[i]) provides dp[4] possibilities.
  • Putting one 2 (i.e., nums[i]) provides dp[3] possibilities.
  • Putting one 3 (i.e., nums[i]) provides dp[2] possibilities.
  • Putting one 4 (i.e., nums[i]) provides dp[1] possibilities.
  • Putting one 5 (i.e., nums[i]) provides dp[0] possibilities.

Therefore, to fully capture dp[5], aggregate all dp[j - nums[i]].

So for combination, the standard formula is:

dp[j] += dp[j - nums[i]]
1

# Summary

This time you might recall, encountered prior in 0039.Combination Sum (opens new window), deployable with dp for simple counts, but demanding recursion for exhaustive details, rendering backtracking optimal.

Here complexity lies in comprehension, relatively achievable via 2D DP, whilst directly efficient employing 1D DP.

Select whichever approach best complements understanding.

For ensuing problems resolving knapsack capacity completion queries, recursive formulas generally apply:

dp[j] += dp[j - nums[i]];
1

Such understanding continues essential later when thoroughly exploring knapsack permutations!

Last updated:: 9/4/2025, 3:19:38 PM

← 14. Ones and Zeroes →

Copyright © 2025 keetcoder