题目要求
输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
分析
考察回溯算法
拿上边的输入举例，每一层就相当于一棵有四个子节点的树， 节点分别是2， 3， 6， 7 重点在于如何去重
会出现的重复的是[2, 2, 3], [2, 3, 2,], [3, 2, 2], 所以档处理到第i个数字的时候，下一层只能考虑[i, candidates.size()-1]中的数字，这样就避免了[3, 2, 2]的出现以及[2, 3, 2]的出现
AC代码
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if (candidates.empty()) {
return {};
}
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0);
return ans;
}
void dfs(vector<int>& candidates, int target, int start) {
if (target < 0) {
return;
}
if (target == 0) {
ans.push_back(tmp);
return;
}
for (int i = start; i < candidates.size(); i++) {
tmp.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i);
tmp.pop_back();
}
}
};
