题目：

 

 

解答：

 

 

 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 
15         for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) 
16         {
17             if (i > start && candidates[i] == candidates[i - 1])
18                 continue;
19             path.push_back(candidates[i]);
20             // 元素不可重复利用，使用下一个即i+1
21             DFS(i + 1, target - candidates[i]);
22             path.pop_back();
23         }
24     }
25 
26     vector<vector<int>> combinationSum2(vector<int> &candidates, int target) 
27     {
28         sort(candidates.begin(), candidates.end());
29         this->candidates = candidates;
30         DFS(0, target);
31         return res;
32     }
33 };