Combination Sum:所有数都正数，原始数组中没有重复的数字，生成的子数组中可以重复使用某一个数值
Combination Sum II ： 所有数都正数，原始数组中有重复的数字，生成的子数组中不能重复使用某一个数值
Combination Sum III： 所有数都正数且只能是1到9之间的数，原始数组中没有重复的数字，生成的子数组中不能重复使用某一个数值
Combination Sum IV: 所有数都正数，原始数组中没有重复的数字，生成的子数组中可以重复使用某一个数值。但是这个不再是把所有的子数组找出来，而是找所有可能的子数组的个数。
39. Combination Sum
依旧与subsets问题相似，每次选择这个数是否参加到求和中。相对于subsets问题，增加一个target变量用于记录数值的和，并且result的push_back的条件也随之发生变化。
因为所有数字都是大于0的，所以target小于0就可以结束循环了。
因为是可以重复的，所以每次递归还是在i上，如果不能重复，就可以变成i+1。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> res;
int length = candidates.size();
if(length <= )
return result;
combination(candidates,result,res,target,);
return result;
}
void combination(vector<int> candidates,vector<vector<int>> &result,vector<int> &res,int target,int start){
if(target < )
return;
if(target == ){
result.push_back(res);
}
for(int i = start;i < candidates.size();i++){
res.push_back(candidates[i]);
combination(candidates,result,res,target-candidates[i],i);
res.pop_back();
}
}
};
https://www.jianshu.com/p/b2037dd2841a
类似于全排列和n皇后，用dfs形成一个n * m的matrix的遍历形式
40. Combination Sum II
与39题的不同在于：第一，本题有重复节点；第二，每个节点只能用一次，即没有自环
如何处理自环问题？每次搜索新路径的时候都从其下一个节点开始，而不是从它本身开始；
如何处理去重问题？每次回溯的时候，刚刚被剔除的节点不能在任何时候再被重新加入到路径上。如何处理这个“任何时候”呢？要么用map标记被剔除的节点直到路径搜索结束，要么应用排序，将所有有相同出权值的节点都放到一起, 通过排序就可以实现,这样可以方便找到下一个出权值不同的节点。
除了这两个部分，其他的与 Combination Sum一样。
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> res;
int length = candidates.size();
if(length <= || target <= )
return result;
sort(candidates.begin(),candidates.end());
combination(candidates,result,res,target,);
return result;
}
void combination(vector<int> candidates,vector<vector<int>> &result,vector<int> &res,int target,int start){
if(target < )
return;
if(target == ){
result.push_back(res);
return;
}
for(int i = start;i < candidates.size();i++){
res.push_back(candidates[i]);
combination(candidates,result,res,target-candidates[i],i+);
res.pop_back();
while(i < candidates.size() - && candidates[i] == candidates[i+])
i++;
}
}
};
http://www.cnblogs.com/tengdai/p/9257266.html
Combination Sum II是数组里面有重复的数字，但不像I那样允许你在你本身上进行重复，所以要用i+1
216. Combination Sum III
这个题与前两者不同的是，规定了组合的数字的个数，这样你就只能递归到第k层了，相当于在递归截止条件处要增加东西。
还有就是不再是一个输入的数组，而是直接1到9。原本发现需要把1到9输入到数组中，后来发现直接在递归里面写也是可以的。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int> > result;
if(k <= || n <= )
return result;
vector<int> res;
int start = ;
combinationSum3(k,n,result,res,start);
return result;
}
void combinationSum3(int k,int n,vector<vector<int> >& result,vector<int>& res,int start){
if(n < )
return;
if(res.size() == k){
if(n == )
result.push_back(res);
return;
}
for(int i = start;i <= ;i++){
res.push_back(i);
combinationSum3(k,n-i,result,res,i+);
res.pop_back();
}
}
};
377. Combination Sum IV
这个题与39. Combination Sum 几乎一样，但是39. Combination Sum 是找所有可能的组合，这个题是找所有可能的子数组的个数，使用dfs也可以做，但在平台上会超时，采用dp的方式时间复杂度小。
dp[i]表示利用当前数组数字到数字i可以生成的个数。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + );
dp[] = ;
for(int i = ;i <= target;i++){
for(int j = ;j < nums.size();j++){
if(i - nums[j] >= )
dp[i] += dp[i - nums[j]];
}
}
return (int)dp[target];
}
};
注意：[3,33,333]
10000
这种情况，如果vector是int初始化，会报int相加越界的错误
http://www.cnblogs.com/grandyang/p/5705750.html