494

494. Target Sum (Medium)

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

Companies: Facebook, Amazon, Google, Bloomberg, Nuro, Adobe, Uber, Apple, Yahoo

Related Topics:
Array, Dynamic Programming, Backtracking

Similar Questions:

• Expression Add Operators (Hard)
• Ways to Express an Integer as Sum of Powers (Medium)

Solution 1. Top-down DP (DFS + Memo)

Let dp[i][t] be the number of ways to form t using A[0..i]. The answer is dp[N-1][target].

dp[i][t] =    dp[i-1][t+A[i]]  // assign '+' to A[i]
            + dp[i-1][t-A[i]]  // assign '-' to A[i]

dp[-1][t] = (t == 0 ? 1 : 0)

Time complexity: For each A[i], there are two options, + and -, so there are 2^N different combinations.

Space compleixty: memo[N-1] at most has 2^N elements in it. memo[N-2] at most has 2^(N-1) elements in it. ... So in total it takes 1 + 2 + 4 + ... + 2^N = O(2^N) space.

// OJ: https://leetcode.com/problems/target-sum/
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    int findTargetSumWays(vector<int>& A, int target) {
        vector<unordered_map<int, int>> memo(A.size());
        function<int(int, int)> dfs = [&](int i, int target) -> int {
            if (i < 0) return target == 0;
            if (memo[i].count(target)) return memo[i][target];
            return memo[i][target] = dfs(i - 1, target + A[i]) + dfs(i - 1, target - A[i]);
        };
        return dfs(A.size() - 1, target);
    }
};

Solution 2. Bottom-up DP

This solution is the Bottom-up version of Solution 1.

Since dp[i] only depends on dp[i-1], we don't need to store dp[j] (j < i - 1).

// OJ: https://leetcode.com/problems/target-sum
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    int findTargetSumWays(vector<int>& A, int target) {
        unordered_map<int, int> m{{0,1}}, next;
        for (int n : A) {
            next.clear();
            for (auto &[val, cnt] : m) {
                next[val + n] += cnt;
                next[val - n] += cnt;
            }
            swap(m, next);
        }
        return m[target];
    }
};

Solution 3. Bottom-up DP (0-1 Knapsack)

Let's say X is a subset of A and Y is the complement subset of X. We assign + to all numbers in X and - to all numbers in Y.

We have SUM(X) - SUM(Y) = target. Since SUM(Y) = SUM(A) - SUM(X), we have 2 * SUM(X) = target + SUM(A).

So, we want to find a subset whose sum S satisfies 2S = target + SUM(A) (target + SUM(A) >= 0 and (target + SUM(A)) % 2 == 0). This is a 0-1 Knapsack problem.

Let dp[i+1][j] be the number of ways to form sum j using A[0..i]. The answer is dp[N][sum].

dp[i+1][j] =    dp[i][j]                                    // Skip A[i]
              + (j - A[i] >= 0 ? dp[i][j - A[i]] : 0)       // Pick A[i]

dp[0][0] = 1

// OJ: https://leetcode.com/problems/target-sum/
// Author: github.com/lzl124631x
// Time: O(NS)
// Space: O(NS)
class Solution {
    int subsetSum(vector<int> &A, int sum) {
        int N = A.size();
        vector<vector<int>> dp(N + 1, vector<int>(sum + 1));
        dp[0][0] = 1;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= sum; ++j) {
                dp[i + 1][j] = dp[i][j] + (j - A[i] >= 0 ? dp[i][j - A[i]] : 0);
            }
        }
        return dp[N][sum];
    }
public:
    int findTargetSumWays(vector<int>& A, int target) {
        target += accumulate(begin(A), end(A), 0);
        return target < 0 || target % 2 ? 0 : subsetSum(A, target / 2);
    }
};

Or with space-optimization.

// OJ: https://leetcode.com/problems/target-sum
// Author: github.com/lzl124631x
// Time: O(NS)
// Space: O(S)
class Solution {
    int subsetSum(vector<int> &A, int sum) {
        vector<int> dp(sum + 1);
        dp[0] = 1;
        for (int n : A) {
            for (int i = sum; i >= n; --i) {
                dp[i] += dp[i - n];
            }
        }
        return dp[sum];
    }
public:
    int findTargetSumWays(vector<int>& A, int target) {
        target += accumulate(begin(A), end(A), 0);
        return target < 0 || target % 2 ? 0 : subsetSum(A, target / 2);
    }
};

NOTE

Related to 416. Partition Equal Subset Sum (Medium)