leetcode个人题解——#40 Combination Sum2

发布时间：2020-12-14 04:22:43 所属栏目：大数据来源：网络整理

导读：思路：解法和39题类似，改动了两处： 1、因为题目要求每个元素只能出现一次（不代表每个数只能有一个，因为数据中会有重复的数字），所以代码中21行搜索时下一次循环的位置+1； 2、将临时存放答案的vectorvectorint类型改为setvectorint类型，避免重复。 1 c

思路：解法和39题类似，改动了两处：

1、因为题目要求每个元素只能出现一次（不代表每个数只能有一个，因为数据中会有重复的数字），所以代码中21行搜索时下一次循环的位置+1；

2、将临时存放答案的vector<vector<int>>类型改为set<vector<int>>类型，避免重复。

 1 class Solution {
 2 public:
 3     int size = 0;
 4     set<vector<int>> ans;
 5     void search(int pos,vector<int>& candidates,int target,vector<int>& res,int sums){
 6         if(sums == target){
 7             ans.insert(res);
 8             return;
 9         }
10         if (pos >= size) return;
11         for(int i = pos; i < size; i++)
12         {
13             if(candidates[i] > target) return;
14             sums += candidates[i];
15             res.push_back(candidates[i]);
16             if(sums > target){
17                 sums -= candidates[i];
18                 res.pop_back(); 
19                 return;
20             } 
21             search(i + 1,candidates,target,res,sums);
22             sums -= candidates[i];
23             res.pop_back();
24         }
25         
26     }
27     
28     vector<vector<int>> combinationSum2(vector<int>& candidates,int target) {
29         sort(candidates.begin(),candidates.end());
30         size = candidates.size();
31         vector<int> res;
32         search(0,0);
33         vector<vector<int>> out(ans.begin(),ans.end());
34         return out;
35     }
36 };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!