// 这道题小细节很多 // 转为01 背包 思路不好想啊 // dp数组难在如何初始化 // dp 数组 通常比较长
如果跟着「代码随想录」一起学过回溯算法系列的录友，看到这道题，应该有一种直觉，就是感觉好像回溯法可以爆搜出来。
事实确实如此，下面我也会给出响应的代码，只不过会超时，哈哈。
这道题目咋眼一看和动态规划背包啥的也没啥关系。
本题要如何是表达式结果为target，
既然为target，那么就一定有 left组合 - right组合 = target，中的left 和right一定是固定大小的，因为left + right要等于sum，而sum是固定的。
公式来了， left - (sum - left) = target -> left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
在回溯算法系列中，一起学过这道题目回溯算法：39. 组合总和的录友应该感觉很熟悉，这不就是组合总和问题么？
此时可以套组合总和的回溯法代码，几乎不用改动。
当然，也可以转变成序列区间选+ 或者 -，使用回溯法，那就是另一个解法。
但无论哪种回溯法，时间复杂度都是是O(2^n)级别，所以最后超时了。
我也把代码给出来吧，大家可以了解一下，回溯的解法，以下是本题转变为组合总和问题的回溯法代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (S > sum) return 0; // 此时没有方案
if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和
// 以下为回溯法代码
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 需要排序
backtracking(nums, bagSize, 0, 0);
return result.size();
}
};
如何转化为01背包问题呢。
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = S
x = (S + sum) / 2
此时问题就转化为，装满容量为x背包，有几种方法。
大家看到(S + sum) / 2 应该担心计算的过程中向下取整有没有影响。
这么担心就对了，例如sum 是5，S是2的话其实就是无解的，所以：
if ((S + sum) % 2 == 1) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
看到这种表达式，应该本能的反应，两个int相加数值可能溢出的问题，当然本题并没有溢出。
在回归到01背包问题，
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
- 确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[i]种方法
- 确定递推公式
有哪些来源可以推出dp[j]呢？
不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]中方法。
那么如果考虑nums[i]呢，dp[j] = dp[j] + dp[j - nums[i]];
公式右面的dp[j]：填满容量为j的背包（没有考虑nums[i]）有dp[j]种方法，
公式右面的dp[j - nums[i]]：填满容量为j - nums[i]的背包有dp[j - nums[i]]种方法
那么只要搞到nums[i]的话，就应该dp[j]（考虑nums[i]）= dp[j]（没考虑nums[i]） + dp[j - nums[i]]
举一个例子,nums[i] = 2： dp[5] = dp[5] + dp[3]，公式右边的dp[5]没考虑这个2，就有dp[5]种方法。
填满背包容量为3的话，有dp[3]种方法。
那么只需要搞到一个2（nums[i]），有dp[3]方法可以凑齐容量为3的背包，相应的就有多少种方法可以凑齐容量为5的背包。
所以 dp[5]（考虑2） = dp[5]（没考虑2） + dp[3]。
所以求组合类问题的公式，都是类似这种：
dp[j] += dp[j - num[i]]
这个公式在后面在讲解背包解决排列组合问题的时候还会用到！
- dp数组如何初始化
从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1中方法，就是装0件物品。
dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。
- 确定遍历顺序
对于01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。
C++代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (S > sum) return 0; // 此时没有方案
if ((S + sum) % 2 == 1) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
int bagSize = (S + sum) / 2;
int dp[1001] = {1}; // 注意这个语法是第一个元素为1，其他都是0
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
- 时间复杂度O(n * m)，n为正数个数，m为背包容量
- 空间复杂度：O(n)，也可以说是O(1)，因为每次申请的辅助数组的大小是一个常数
dp数组中的数值变化：（从[0 - 4]）
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
1 5 10 10 5
此时 大家应该不仅想起，我们之前讲过的回溯算法：39. 组合总和是不是应该也可以用dp来做啊？
是的，如果仅仅是求个数的话，就可以用dp，但回溯算法：39. 组合总和要求的是把所有组合列出来，还是要使用回溯法爆搜的。