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:
- 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.
这道题给了我们一个数组，和一个目标值，让我们给数组中每个数字加上正号或负号，然后求和要和目标值相等，求有多少中不同的情况。那么对于这种求多种情况的问题，我最想到的方法使用递归来做。我们从第一个数字，调用递归函数，在递归函数中，分别对目标值进行加上当前数字调用递归，和减去当前数字调用递归，这样会涵盖所有情况，并且当所有数字遍历完成后，我们看若目标值为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, int 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); } };
我们对上面的递归方法进行优化，使用dp数组来记录中间值，这样可以避免重复运算，参见代码如下：
解法二：
class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { vector<unordered_map<int, int>> dp(nums.size()); return helper(nums, S, 0, dp); } int helper(vector<int>& nums, int sum, int start, vector<unordered_map<int, int>>& dp) { if (start == nums.size()) return sum == 0; if (dp[start].count(sum)) return dp[start][sum]; int cnt1 = helper(nums, sum - nums[start], start + 1, dp); int cnt2 = helper(nums, sum + nums[start], start + 1, dp); return dp[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]; } };
我们也可以对上面的方法进行空间上的优化，只用一个哈希表，而不是用一个数组的哈希表，我们在遍历数组中的每一个数字时，新建一个哈希表，我们在遍历原哈希表中的项时更新这个新建的哈希表，最后把新建的哈希表整个赋值和原哈希表，参见代码如下：
解法四：
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]; } };
本文转自博客园Grandyang的博客，原文链接：Target Sum 目标和，如需转载请自行联系原博主。
