首页 > 代码库 > leetcode-Combination Sum II-40

leetcode-Combination Sum II-40

2024-08-11 07:59:50   210人阅读

输入一个数组，选择任意个数的元素，求和等于target的所有组合，每个元素只能选择一次，组合不能重复

求组合：先排序，dfs，回溯 

去重：把dfs想象成一颗树，同一层如果元素值相同，那么只对第一个元素深搜，其余相同的元素不必深搜，注意是同一层，看代码注释

 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         for(int j=i+1;j<a.size();j++){10             if(sum+a[j]<=target){11                 if(j!=i+1&&a[j]==a[j-1]) continue;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> > combinationSum2(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(i>0&&candidates[i]==candidates[i-1]) continue;25             if(candidates[i]<=target){26                 vv.push_back(candidates[i]);27                 dfs(v,vv,candidates,i,target,sum+candidates[i]);28                 vv.pop_back();29             }30         }31         return v;32         // if(v.size()==0) return v;33         // vector<vector<int> > ans;34         // ans.push_back(v[0]);35         // int k=0;36         // for(int i=1;i<v.size();i++){37         //     if(v[i].size()!=ans[k].size()){38         //         ans.push_back(v[i]);39         //         k++;40         //         continue;41         //     }42         //     int ok=0;43         //     for(int j=0;j<v[i].size();j++){44         //         if(v[i][j]!=ans[k][j]){45         //             ok=1;break;46         //         }47         //     }48         //     if(ok){49         //         ans.push_back(v[i]);50         //         k++;51         //     }52         // }53         // return ans;54     }55 };

 

leetcode-Combination Sum II-40


联系
我们