力扣算法题—040组合求和二

 1 #include "000库函数.h"
 2 
 3 //第一感觉使用回溯比较快
 4 //96ms
 5 
 6 
 7 class Solution {
 8 public:
 9     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
10         vector<vector<int>>R;
11         sort(candidates.begin(), candidates.end());
12         if (candidates.size() == 0)return R;
13         vector<int>v;//临时存放解    
14         Combin(candidates, R, v, target, 0, 0);        
15         return R;
16     }
17 
18     void Combin(vector<int>candidates, vector<vector<int>>&Res, vector<int>&v, int target, int start, int sum) {
19         if (sum == target) {
20             //sort(v.begin(), v.end());
21             Res.push_back(v);
22             return;
23         }
24         else if (sum > target)
25             return;
26 
27         for (int i = start; i < candidates.size(); ++i) {
28             if (i > start&&candidates[i] == candidates[i - 1])continue;//去除重复的组合            
29             v.push_back(candidates[i]);
30             Combin(candidates, Res, v, target, i + 1, sum + candidates[i]);//i+1是与上题的不同之处，不会出现重复使用元素
31             v.pop_back();//将数字退出                
32         }
33     }
34 
35 };
36 
37 void T040() {
38     vector<int> v;
39     vector<vector<int>>Res;
40     Solution s;
41     v = {10,1,2,7,6,1,5 };
42     Res = s.combinationSum2(v, 8);
43     for (auto &a : Res) {
44         for (auto b : a)
45             cout << b << "  ";
46         cout << endl;
47     }
48     cout << endl << "*********" << endl;
49     /*v = { 2, 3,5 };
50     Res = s.combinationSum(v, 8);
51     for (auto &a : Res) {
52         for (auto b : a)
53             cout << b << "  ";
54         cout << endl;
55     }
56     cout << endl << "*********" << endl;
57 */
58 
59 
60 }