代码随想录算法训练营第二十二天| 39. 组合总和 40.组合总和II 131.分割回文串

 1 void combinationSum_trackBack(vector<int>& candidates, int target,
 2     int sum_,int startIndex, vector<int>& path, vector<vector<int>>& result)
 3 {
 4     if (sum_ > target)
 5         return;
 6     if (sum_ == target)
 7     {
 8         result.push_back(path);
 9         return;
10     }
11 
12     for (int i = startIndex; i < candidates.size(); i++)
13     {
14         sum_ += candidates[i];
15         path.push_back(candidates[i]);
16         combinationSum_trackBack(candidates, target, sum_,i, path, result);
17         path.pop_back();
18         if (sum_ > target)
19         {
20             return;
21         }
22         sum_ -= candidates[i];
23     }
24 }
25 
26 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
27     vector<vector<int>>result;
28     if (candidates.size() == 0) return result;
29 
30     set<map<int, int>> check_dup;
31     vector<int>path;
32     sort(candidates.begin(), candidates.end());
33     combinationSum_trackBack(candidates, target,0,0, path, result);
34     return result;
35 }