LC39 Combination Sum-白红宇

LC39 Combination Sum

阅读量：6882 次

发布时间：2019-06-27

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

还是利用深搜的思想，注意一个元素可以取无数次。而LC40 Combination Sum II 就有次数限制，有次数限制的情况下可以先判断一个数是否与它前面的数相等，若相等则跳过该元素，直到找到一个数与它前面的数不等，再进行深搜。

这里附上LC39的代码

1 class Solution { 2 public: 3     vector
      
       
        > result; 4     void dfs(int start,int n,int target,vector
        
         & cand,vector
         
           record) 5     { 6         int tar; 7         for(int i=start;i

rec=record;11 if(tar

=cand[i])14 {15 tar-=cand[i];16 rec.push_back(cand[i]);17 if(tar==0)18 {19 result.push_back(rec);20 break;21 }22 else if(tar

> combinationSum(vector

& candidates, int target) {29 if(candidates.size()==0||target<=0)30 return result;31 sort(candidates.begin(),candidates.end());32 vector

record;33 dfs(0,candidates.size(),target,candidates,record);34 return result;35 }36 };

View Code

附上一段更简洁的代码

1 class Solution { 2 public: 3     vector
      
       
         > combinationSum(vector
        
          &nums, int target) { 4         sort(nums.begin(), nums.end()); 5         vector
         
          
            > result;   6         vector
           
             intermediate; 7 dfs(nums, target, 0, intermediate, result); 8 return result; 9 }10 private:11 void dfs(vector
            
             & nums, int gap, int start, vector
             
              & intermediate,12 vector
              
               
                 > &result) {13 if (gap == 0) { 14 result.push_back(intermediate);15 return;16 }17 for (size_t i = start; i < nums.size(); i++) { 18 if (gap < nums[i]) return; 19 intermediate.push_back(nums[i]); 20 dfs(nums, gap - nums[i], i, intermediate, result);21 intermediate.pop_back(); 22 }23 }24 };

View Code

转载于:https://www.cnblogs.com/vaecn/p/5350152.html