1 回溯法（AC，29�at，745ms）
谁说这道题回溯法就不能AC？我偏要AC！！
回溯法需做好剪枝优化和记录结果的数据结构不能太复杂就能飘过，比如不能用vector记录结果
class Solution {
private:
int size;
int count = 0;
int sum = 0;
public:
void backtrack(vector<int>& nums, int curSum, int first) {
if (curSum == sum) count ; // [关键]:不能有return，因为一个序列可能存在多个组合(分布在前或后)
for (int i = first; i < size; i ) {
if (curSum nums[i] > sum) break; // 该剪枝可省时约200ms
backtrack(nums, curSum nums[i], i 1); // 直接传入而不先 后--可省时约1000ms
}
}
int findTargetSumWays(vector<int>& nums, int S) {
size = nums.size();
// 排序——回溯时将所有过大节点排序到靠右分支以方便批量剪枝
sort(nums.begin(), nums.end());
sum = accumulate(nums.begin(), nums.end(), 0);
// 排除，S过大 || (sum S)是奇数的情况
if (sum < S || (sum S) % 2 != 0) return 0;
sum = (sum S) / 2;
backtrack(nums, 0, 0);
return count;
}
};2 动态规划-01背包（AC，92�at，8ms）
【dp数组含义】：容量(和)为j的情况下，恰好装满容量j(和)的方案数为dp[j]个
【状态转移方程】：dp[j] = dp[j] dp[j - nums[i]]
比如元素nums = [1, 2, 2, 3, 3, 5], S = 8，则有dp[8] = 8，每个方案对应组合如下
(1, 2, 3, 3)->2个
(2, 3, 3) ->2个
#################
(3, 5) ->2个
(1， 2, 5) ->2个已知dp[3]恰好装满容量为3的背包方案数是4个，(1, 2, 2, [5])->2个 (3, 3, [5]) ->2个 = 4
- 不装
nums[5] = 5，dp[8]方案有(1, 2, 3, 3)->2个 (2, 3, 3) ->2个 = 4 - 装
nums[5] = 5，dp[8] = dp[8-5]有(1, 2, 2, [5])->2个 (3, 3, [5]) ->2个 = 4 - 可见，
dp[8] = dp[8] dp[8 - 5] = 4 4 = 8
写好状态转移方程后最重要的就是初始化，dp[0] = 1
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum < S || (sum S) % 2 != 0) return 0;
sum = (sum S) / 2;
vector<int> dp(sum 1, 0);
dp[0] = 1; // [关键]：根据状态转移方程，dp[0]须为1
for (int i = 0; i < nums.size(); i )
for (int j = sum; j >= nums[i]; j--) {
dp[j] = dp[j] dp[j - nums[i]];
}
return dp[sum];
}
};
