leetcode: combination sum 系列解题思路

 刷题刷到这里了，就码点字，别让自己得过且过了~
言归正传，这一系列的题目大体框架是给你一个数组和一个目标数，要求让我们从所给数组中挑选出一些列数字相加的和恰好等于目标数的排列数，当然了，其中加点限制是不可避免的。
I. 限制条件：可以重复抽取同一数字，但是重复的排列不算数。比较简单的回溯，对于每个nums中的数字，两种选择，放或者不放，依次递归就行了，代码如下：

点击(此处)折叠或打开

1. vector<vector<int>> combinationSum(vector<int>& candidates, int target){
   
2.     int len = candidates.size();
   
3.     vector<vector<int>> res;
   
4.     if(len == 0) return res;
   
5.     sort(candidates.begin(), candidates.end());
   
6.     vector<int> combo;
   
7.     helper(candidates, target, combo, 0, len-1, res);
   
8.     return res;
   
9. }
   
10. void helper(vector<int>& candidates, int target, vector<int>& combo, int start, int end, vector<vector<int> > &res){
    
11.     if(target == 0){
    
12.         res.push_back(combo);
    
13.         return;
    
14.     }
    
15.     for(int i = start; i <= end&&target>=candidates[i];i++){
    
16.         combo.push_back(candidates[i]);
    
17.         helper(candidates, target-candidates[i], combo, i, end, res);
    
18.         combo.pop_back();
    
19.     }
    
20. }

注意，因为是从集合中抽取，所以最好先排个序
II.限制条件：每一个在nums数组中的数，最多只能放一次。思路同上，代码如下：

点击(此处)折叠或打开

1. vector<vector<int>> combinationSum2(vector<int>& candidates, int target){
   
2.     int len = candidates.size();
   
3.     vector<vector<int>> res;
   
4.     if(len == 0) return res;
   
5.     sort(candidates.begin(), candidates.end());
   
6.     vector<int> combo;
   
7.     helper2(candidates, target, combo, 0, len-1, res);
   
8.     return res;
   
9. }
   
10. void helper2(vector<int>& candidates, int target, vector<int>& combo, int start, int end, vector<vector<int> > &res){
    
11.     if(target == 0){
    
12.         res.push_back(combo);
    
13.         return;
    
14.     }
    
15.     for(int i = start; i <= end&&target>=candidates[i];i++){
    
16.        if(i==start || candidates[i]!=candidates[i-1])// avoid repeat results
    
17.         {
    
18.             combo.push_back(candidates[i]);
    
19.             helper2(candidates, target-candidates[i], combo, i+1, end, res);
    
20.             combo.pop_back();
    
21.         }
    
22.     }
    
23. }

III. 限制条件：nums数组变为1-9这几个数字了，思路同2题，代码如下，不过他要求恰好用k个数，需要注意下：

点击(此处)折叠或打开

1. vector<vector<int>> combinationSum3(int k, int n){
   
2.     int need = k, target = n;
   
3.     vector<vector<int>> res;
   
4.     vector<int> combo;
   
5.     if(n==0)return res;
   
6.     helper3(res, combo, target, 1, need);
   
7.     return res;
   
8. }
   
9. void helper3(vector<vector<int>>& res, vector<int> &combo, int target,int start, int need){
   
10.     if(target == 0&& need ==0){
    
11.         res.push_back(combo);
    
12.         return;
    
13.     }
    
14.     if(need == 0) return;
    
15.     for(int i = start; i <=9&&target>=i&&target<=need*9-need*(need-1)/2; i++){
    
16.         combo.push_back(i);
    
17.         helper3(res, combo, target-i, i+1, need-1);
    
18.         combo.pop_back();
    
19.     }
    
20. }

IV限制条件：思路同题目I，但是求的不是组合，而是组合的个数，偷偷的以为可以直接第一题代码改成个数，复制粘贴就可以了，但是超时。。。只好dp了；dp思路：dp[i]代表整个数组求求和到i的总组合数，递推为ifif(i >= nums[j]) dp[i]+=dp[i-nums[j]];代码如下：

点击(此处)折叠或打开

1. int combinationSum4(vector<int>& nums, int target){
   
2.     int len = nums.size(), i, j;
   
3.     if(len == 0) return 0;
   
4.     vector<int> dp(target+1);
   
5.     dp[0] = 1;
   
6.     for(i = 1; i <= target; i++){
   
7.         for(j = 0; j < len; j++){
   
8.             if(i >= nums[j]) dp[i]+=dp[i-nums[j]];
   
9.         }
   
10.     }
    
11.     return dp[target];
    
12. }

总结：少年，路还很远~~