39. Combination Sum

因为是可以重复的，所以每次递归还是在i上，如果不能重复，就可以变成i+1

class Solution {public:    vector
     
      
       > combinationSum(vector
       
        & candidates, int target) {        vector
        
         
          > result;        vector
          
            res; int length = candidates.size(); if(length <= 0) return result; combination(candidates,result,res,target,0); return result; } void combination(vector
           
             candidates,vector
            
             
              > &result,vector
              
                &res,int target,int start){ if(target < 0) return; if(target == 0){ 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标记被剔除的节点直到路径搜索结束，要么应用排序，将所有有相同出权值的节点都放到一起，这样可以方便找到下一个出权值不同的节点。

想完这两个不同点，这道题就解决了。

class Solution {public:    vector
     
      
       > combinationSum2(vector
       
        & candidates, int target) {        vector
        
         
          > result;        vector
          
            res; int length = candidates.size(); if(length <= 0 || target <= 0) return result; sort(candidates.begin(),candidates.end()); combination(candidates,result,res,target,0); return result; } void combination(vector
           
             candidates,vector
            
             
              > &result,vector
              
                &res,int target,int start){ if(target < 0) return; if(target == 0){ 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+1); res.pop_back(); while(i < candidates.size() - 1 && candidates[i] == candidates[i+1]) i++; } }};
              
             
            
           
          
         
        
       
      
     

http://www.cnblogs.com/tengdai/p/9257266.html

 Combination Sum II是数组里面有重复的数字，但不像I那样允许你在你本身上进行重复，所以要用i+1