组合总和
- 难度： 中等
- 通过率： 45.4%
- 题目链接：https://leetcode-cn.com/problems/combination-sum
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates =[2,3,6,7],target =7, 所求解集为: [ [7], [2,2,3] ]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解法：
采用深度优先搜索来搜索解空间。先对数组由小达大排序，每次取一个数字，然后把 target 减掉此值，然后在此数及之后的数中继续寻找。
对数组进行排序，是为了避免重复，选取的下一个数字必须等于等于前一个。这样就不会出现 1 + 2 = 3 和 2 + 1 = 3 这样的重复组合了。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> result;
vector<int> path; // 中间结果
dfs(candidates, path, result, 0, target);
return result;
}
void dfs(const vector<int>& candidates, vector<int>& path,
vector<vector<int>>& result, size_t start, int target){
if(target == 0){
result.push_back(path);
}
auto it = candidates.begin() + start;
while(it != candidates.end()){
if(target < *it){
return;
}
path.push_back(*it);
dfs(candidates, path, result, it - candidates.begin(), target - *it);
path.pop_back();
++it
}
}
};