494. Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 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 nums be target 3.

Note:

1. The length of the given array is positive and will not exceed 20.

2. The sum of elements in the given array will not exceed 1000.

3. Your output answer is guaranteed to be fitted in a 32-bit integer.

利用Top-Down Recursion加上memoization避免重複計算。每一層只有兩種選擇，加或減。

// Top-Down DP with Memoization
int helper(const vector<int>& nums, int i, int sum, int S, unordered_map<string, int>& memo) {
    string keyStr = to_string(i) + "_" + to_string(sum);
    if (memo.count(keyStr)) return memo[keyStr];
    if (i == nums.size()) {
        return sum == S ? 1 : 0;
    }
    int num = nums[i];
    int add = helper(nums, i + 1, sum + num, S, memo);
    int minus = helper(nums, i + 1, sum - num, S, memo);
    int res = add + minus;
    return memo[keyStr] = res;
}
int findTargetSumWays(vector<int>& nums, int S) {
    unordered_map<string, int> memo;
    return helper(nums, 0, 0, S, memo);
}

這個問題類似knapsack 0/1問題，可以把input array分成正數group和負數group，分別用P和N代表。P和N為nums的subset。 sum(P) - sum(N) = target sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N) 2 * sum(P) = target + sum(nums) sum(P) = (target + sum(nums)) / 2 由此可知target + sum(nums)必須為even number。 如果sum(nums)小於target S，那這題沒有任何正負組合滿足條件。 利用2-D dp array去紀錄，維度為(nums.size() + 1) * (S + 1)。 dp[i][j]代表利用前i個elements去得到j的和的總方法數量。 dp[i][j] = dp[i - 1][j] + dp[i -1][j - nums[i - 1]] dp[i - 1][j]代表不用nums[i - 1]就達到和為j的方法數量，dp[i - 1][j - nums[i - 1]]代表使用nums[i - 1]達到和為j的方法數量。

// Bottom-Up 2-D DP
int subsetSum(const vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<int> > dp(n + 1, vector<int> (target + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= target; ++j) {
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp.back().back();
}
int findTargetSumWays(vector<int>& nums, int S) { // time: O(n * S); space: O(n * S)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    return (sum < S || (sum + S) & 0x1) ? 0 : subsetSum(nums, (sum + S) >> 1);
}

可以優化dp array空間使用，因為每個dp[i][j]都與前一個row的兩個值有關，所以可以降維至1-D array。 dp[j] = dp[j] + dp[j - nums[i - 1]]。 要注意loop的順序是從大的和到小的和。因為這樣才能避免重複算到當前這個row達成j - nums[i - 1]的結果。

// Bottom-Up 1-D DP
int subsetSum(const vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = target; j >= nums[i]; --j) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp.back();
}
int findTargetSumWays(vector<int>& nums, int S) { // time: O(n * S); space: O(S)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    return (sum < S || (sum + S) & 0x1) ? 0 : subsetSum(nums, (sum + S) >> 1);
}

和的範圍在-sum ~ +sum之間，總共有2 * sum + 1個可能。如果想要利用dp array的index對應到這些sum的可能，那就需要把sum range平移，-sum ~ +sum可以變成sum ~ 2 * sum。 dp[i][j]代表的就是前i個elements組成j - sum的和的所有方法數量。 dp[i][j] += dp[i - 1][j + nums[i - 1]] + dp[i - 1][j - nums[i - 1]]

// Dynamic Programming
int findTargetSumWays(vector<int>& nums, int S) { // time: O(n * S); space: O(n * S)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (S > sum || S < -sum) return 0;
    int n = nums.size(), leftBound = 0, rightBound = 2 * sum;
    vector<vector<int> > dp(n + 1, vector<int> (2 * sum + 1, 0));
    dp[0][sum] = 1; // -sum ~ sum => 0 ~ 2*sum
    for (int i = 1; i <= n; ++i) {
        for (int j = leftBound; j <= rightBound; ++j) {
            if (j + nums[i - 1] <= rightBound)
                dp[i][j] += dp[i - 1][j + nums[i - 1]];
            if (j - nums[i - 1] >= leftBound)
                dp[i][j] += dp[i - 1][j - nums[i - 1]];
        }
    }
    return dp[n][sum + S];
}

tmp可以用來暫時存下之後的dp array的資料，每一個iteration在複製給dp。

// Space Optimized 1-D Dynamic Programming
int findTargetSumWays(vector<int>& nums, int S) { // time: O(n * S); space: O(S)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (S > sum || S < -sum) return 0;
    int n = nums.size();
    vector<int> dp(2 * sum + 1, 0);
    dp[sum] = 1; // -sum ~ sum => 0 ~ 2*sum
    for (int i = 0; i < n; ++i) {
        vector<int> tmp(2 * sum + 1, 0);
        for (int j = 0; j <= 2 * sum; ++j) {
            if (dp[j] != 0) {
                tmp[j + nums[i]] += dp[j];
                tmp[j - nums[i]] += dp[j];
            }
        }
        dp = tmp;
    }
    return dp[sum + S];
}