494. Target Sum

https://leetcode.com/problems/target-sum/

Problem

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.

Constraints:

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

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

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

Solution

1. Naive DP

class Solution {
public:  
    int findTargetSumWays(vector<int>& nums, int S){
        const int size = nums.size();
        int sum = 0;
        for (const auto n: nums) sum += n;
        if (sum < S) return 0;
        if (S < 0) S = -S;
        int dp[size + 1][sum + 1];
        memset(dp, 0, sizeof(int) * (size + 1) * (sum + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= size; ++i) {
            for (int s = 0; s <= sum; ++s) {
                dp[i][s] += dp[i - 1][abs(s - nums[i - 1])];
                if (nums[i - 1] + s <= sum) dp[i][s] += dp[i - 1][s + nums[i - 1]];
            }
        }
        return dp[size][S];
    }
};

2. Optimized DP

$$\begin{array}{rcl} Sum & = & a + b \\ S & = & a - b ~( a \ge b) \end{array}$$

$$\therefore ~ Sum + S = 2a$$

class Solution {
public:  
    int findTargetSumWays(vector<int>& nums, int S){
        const int size = nums.size();
        long long sum = 0;
        for (const auto n: nums) sum += n;
        if ((sum + S) % 2 != 0 || sum < S) return 0;
        const int T = (sum + S) / 2 + 1;
        int dp[T];
        memset(dp, 0, T * sizeof(int));
        dp[0] = 1;
        for (int i = 0; i < nums.size(); ++i) {
            for (int s = T - 1; s >= nums[i]; --s) {
                dp[s] += dp[s - nums[i]];
            }
        }
        return dp[T - 1];
    }
};

• #veryimportant

• #dp

• #math