题目：

 

 

解答：

 

 https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

 1 class Solution {
 2 private:
 3     vector<int> candidates;
 4     vector<vector<int>> res;
 5     vector<int> path;
 6 public:
 7     void DFS(int start, int target) 
 8     {
 9         if (target == 0) 
10         {
11             res.push_back(path);
12             return;
13         }
14         for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) 
15         {
16             path.push_back(candidates[i]);
17             DFS(i, target - candidates[i]);
18             path.pop_back();
19         }
20     }
21 
22     vector<vector<int>> combinationSum(vector<int> &candidates, int target) 
23     {
24         std::sort(candidates.begin(), candidates.end());
25         this->candidates = candidates;
26         DFS(0, target);
27 
28         return res;
29     }
30 };