本文共 1017 字，大约阅读时间需要 3 分钟。

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。 

示例 1:

输入: candidates = [2,3,6,7], target = 7,所求解集为:[  [7],  [2,2,3]]

示例 2:

输入: candidates = [2,3,5], target = 8,所求解集为:[  [2,2,2,2],  [2,3,3],  [3,5]]

 因为全是正数，所以，当dfs中的sum>target时，不必再进行dfs了，减去这种情况。

每一次往下dfs时，要在>=这个数的位置进行搜索。

C++：

class Solution {public:    vector
   
    
     > combinationSum(vector
     
      & candidates, int target) {        int Size=candidates.size();        vector
      
       
        >ve;        vector
        
          te; if(Size==0) return ve; dfs (0,target,candidates,ve,te,Size,0); return ve; } void dfs (int sum,int target,vector
         
          & v1,vector
          
           
            >& re,vector
            
             & te,int Size,int loc) { if(sum==target) { re.push_back(te); return; } for (int i=loc;i
             
              target) continue; te.push_back(v1[i]); dfs (sum+v1[i],target,v1,re,te,Size,i); te.pop_back(); } }};
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://qvaen.baihongyu.com/