[LeetCode] 494. Target Sum

[grandyang]

 

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.

 

这道题给了我们一个数组，和一个目标值，让给数组中每个数字加上正号或负号，然后求和要和目标值相等，求有多少中不同的情况。那么对于这种求多种情况的问题，博主最想到的方法使用递归来做。从第一个数字，调用递归函数，在递归函数中，分别对目标值进行加上当前数字调用递归，和减去当前数字调用递归，这样会涵盖所有情况，并且当所有数字遍历完成后，若目标值为0了，则结果 res 自增1，参见代码如下：

 

解法一：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int res = 0;
        helper(nums, S, 0, res);
        return res;
    }
    void helper(vector<int>& nums, long S, int start, int& res) {
        if (start >= nums.size()) {
            if (S == 0) ++res;
            return;
        }
        helper(nums, S - nums[start], start + 1, res);
        helper(nums, S + nums[start], start + 1, res);
    }
};

 

我们对上面的递归方法进行优化，使用 memo 数组来记录中间值，这样可以避免重复运算，参见代码如下：

 

解法二：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        vector<unordered_map<int, int>> memo(nums.size());
        return helper(nums, S, 0, memo);
    }
    int helper(vector<int>& nums, long sum, int start, vector<unordered_map<int, int>>& memo) {
        if (start == nums.size()) return sum == 0;
        if (memo[start].count(sum)) return memo[start][sum];
        int cnt1 = helper(nums, sum - nums[start], start + 1, memo);
        int cnt2 = helper(nums, sum + nums[start], start + 1, memo);
        return memo[start][sum] = cnt1 + cnt2;
    }
};

 

我们也可以使用迭代的方法来解，使用一个 dp 数组，其中 dp[i][j] 表示到第 i-1 个数字且和为j的情况总数，参见代码如下：

 

解法三：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        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 &a : dp[i]) {
                int sum = a.first, cnt = a.second;
                dp[i + 1][sum + nums[i]] += cnt;
                dp[i + 1][sum - nums[i]] += cnt;
            }
        }
        return dp[n][S];
    }
};

 

我们也可以对上面的方法进行空间上的优化，只用一个 HashMap，而不是用一个数组的哈希表，在遍历数组中的每一个数字时，新建一个 HashMap，在遍历原 HashMap 中的项时更新这个新建的 HashMap，最后把新建的 HashMap 整个赋值为原 HashMap，参见代码如下：

 

解法四：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        unordered_map<int, int> dp;
        dp[0] = 1;
        for (int num : nums) {
            unordered_map<int, int> t;
            for (auto a : dp) {
                int sum = a.first, cnt = a.second;
                t[sum + num] += cnt;
                t[sum - num] += cnt;
            }
            dp = t;
        }
        return dp[S];
    }
};

 

Github 同步地址：

#494

 

类似题目：

Expression Add Operators

 

参考资料：

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

https://leetcode.com/problems/target-sum/discuss/97371/Java-Short-DFS-Solution

https://leetcode.com/problems/target-sum/discuss/97369/Evolve-from-brute-force-to-dp

https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

解法4中 dp=t 成本太高， 应该用dp.swap(t) 或者 dp = move(t);

[lld2006]

高票解法出现在2018年十月， 非常精彩。 算法如下
Sum(positive)-Sum(negative)=S // target
Sum(positive)+Sum(negative)=total // sum of all numbers

So, 两式相加得

2 Sum(positive) = (S+total);
所以题目等价于从nums里任取若干使其和为（S+total)/2（S, total奇偶性必需相同）, 这样就成了knapsack problem， 参考崔天翼的背包九讲中最基本的形式， 可以得到如下code

class Solution {
public:
int findTargetSumWays(vector& nums, int sum) {
int total = accumulate(nums.begin(), nums.end(), 0);
if(sum > total || sum< -total) return 0;
if((total + sum) & 1 ) return 0;
int target = (total + sum) >> 1;
vector dp(target+1, 0);//0...to target, inclusive
dp[0] = 1;
for(auto n : nums){
int k0 = static_cast(dp.size()) - 1-n;
for(int k = k0; k >=0; --k)
dp[k+n] += dp[k];
}
return dp.back();
}
};

[baicaihenxiao]

Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation