leetcode 39. Combination Sum 、40. Combination Sum II 、216. Combination Sum III

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

上一篇:【LeetCode】40. Combination Sum II 解题报告(Python & C++)


下一篇:VS2012 Unit Test —— 我对IdleTest库动的大手术以及对Xml相关操作进行测试的方式