首页 > 代码库 > leetcode-Combination Sum-39

leetcode-Combination Sum-39

2024-08-11 08:00:13   211人阅读

输入一个数组和target，选择任意个数的元素，求和为target的组合，每个元素可以选择多次

dfs，回溯，因为每个元素可以选择多次，所以向下搜索的时候从当前元素开始

同类题：http://blog.csdn.net/AC_0_summer/article/details/48293581

 1 class Solution { 2 public: 3     void dfs(vector<vector<int> > &v,vector<int> vv,vector<int> a,int i,int target,int sum){ 4         if(sum>target) return; 5         if(sum==target){ 6             v.push_back(vv); 7             return; 8         } 9        // vv.push_back(a[i]);10         for(int j=i;j<a.size();j++){11             if(sum+a[j]<=target){12                 vv.push_back(a[j]);13                 dfs(v,vv,a,j,target,sum+a[j]);14                 vv.pop_back();15             }16         }17     }18     vector<vector<int> > combinationSum(vector<int>& candidates, int target) {19         vector<vector<int> > v;20         vector<int> vv;21         int sum=0;22         sort(candidates.begin(),candidates.end());23         for(int i=0;i<candidates.size();i++){24             if(candidates[i]<=target){25                 vv.push_back(candidates[i]);26                 dfs(v,vv,candidates,i,target,sum+candidates[i]);27                 vv.pop_back();28             }29         }30         if(v.size()==0) return v;31         vector<vector<int> > ans;32         ans.push_back(v[0]);33         int k=0;34         for(int i=1;i<v.size();i++){35             if(ans[k].size()!=v[i].size()){36                 ans.push_back(v[i]);37                 k++;38                 continue;39             }40             int ok=0;41             for(int j=0;j<ans[k].size();j++){42                 if(v[i][j]!=ans[k][j]){43                     ok=1;break;44                 }45             }46             if(ok){47                 ans.push_back(v[i]);48                 k++;49             }50         }51         return ans;52     }53 };

 

leetcode-Combination Sum-39


联系
我们