LeetCode 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.

---

给定一个数组nums，和目标结果S，要求给数组中的每个数加上符号+或-，使得和为S。问共有多少种加符号的方案。 第一反应是DFS，遍历每个数，对其加上+或者-，更新S，然后递归。当遍历完所有数，且和等于0时，找到一种方案。 代码如下： [cpp] class Solution { private: void dfs(vector<int>& nums, int step, int S, int& ans) { if (step == nums.size() && S == 0) { ++ans; return; } if (step == nums.size())return; dfs(nums, step + 1, S – nums[step], ans); dfs(nums, step + 1, S + nums[step], ans); } public: int findTargetSumWays(vector<int>& nums, int S) { int ans = 0; dfs(nums, 0, S, ans); return ans; } }; [/cpp] 本代码提交AC，用时1072MS。居然需要这么长时间，果断优化。 思来想去，这本质是一个背包问题，常规0/1背包是对每个商品要还是不要，这题的背包是，对每个数字，是加正号还是负号。 假设dp[i][j]表示前i个数字之和为j的不同加符号方案数，则有如下递归公式 dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]] 右边第一项是指对第i个数字，要赋加号，那么就要保证前i-1个数字之和是j-nums[i]，这样(j-nums[i])+nums[i]才会等于j。类似的，如果要对第i个数字赋减号，就要保证前i-1个数字之和是j+nums[i]。所以总的就是这两种情况加和。 需要注意的是，因为可以赋负号，所以加和的结果可能是负数（范围是[-sum,sum]），为了dp[i][j]中的j能用下标访问，统一把所有和加上总和sum，做一个偏移（范围是[0,2*sum]），最终结果就是dp[n][S+sum]。 DP的代码如下： [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; //if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0 vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0)); dp[0][sum] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2 * sum + 1; ++j) { //考虑第i个数字是+还是- //i从1开始，所以第i个数字的下标是i-1 if (j >= nums[i – 1])dp[i][j] += dp[i – 1][j – nums[i – 1]]; if (j + nums[i – 1] < 2 * sum + 1)dp[i][j] += dp[i – 1][j + nums[i – 1]]; } } return dp[n][S + sum]; } }; [/cpp] 本代码提交AC，用时19MS，加速将近100倍！ DP的问题一般都可以优化空间，比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。 上面的DP公式理解起来还是有点费劲，下面介绍另一种DP思路，非常简单。 假设我们已经求到前i-1个数字赋不同的符号可以得到的不同和的方案数了，也就是dp[pre]数组，现在要求对第i个数字赋不同符号可能得到的不同和的方案数。那么我们可以遍历dp[pre]数组，只要某个和j对应的方案数不为0（dp[pre][j]!=0），则说明前i-1个数能够组合出和j，且和为j的方案数正好是dp[pre][j]，那么我们只需要在和j的基础上考虑加nums[i]或者减nums[i]，如果对应的j+nums[i]或j-nums[i]没有超出范围，则这一轮和为j+nums[i]的方案数要加上上一轮和为j的方案数，这一轮和为j-nums[i]的方案数要加上上一轮和为j的方案数。 最后返回dp[cur][S+sum]。非常好理解的一个思路。用这种思路还可以求出从给定数组中取任意多个数相加，可以得到的不同和的方案数，其实和这个题类似，只不过把每个数字的状态改为了取和不取。 代码如下： [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0)); int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1; dp[pre][sum] = 1; // 取0个数字，加和为0的方案有1种。把和0偏移到sum位置 while (i < n) { pre = (i & 1) ? 1 : 0; cur = (i & 1) ? 0 : 1; for (int j = 0; j < 2 * sum + 1; ++j) { if (dp[pre][j] != 0) { if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i] if (j – nums[i] >= 0)dp[cur][j – nums[i]] += dp[pre][j]; // 在j的基础上减nums[i] } } fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组，因为下一轮pre要用作cur数组 ++i; } return dp[cur][S + sum]; } }; [/cpp] 本代码提交AC，用时13MS。用了两个滚动数组，空间效率高一点。 ]]>