题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
难度
中等
题解
从给定范围内寻求所有可行解，可以使用搜索回溯来解决。
题中已说明candidates中的元素可以无限制重复使用，那么最直观的方法就是直接for循环遍历一遍，看能不能找到两个元素构成target，不行的话再来一遍，看能不能找的三个元素构成target，直到执行了candidates.size()个for循环。这时候，递归可以解决这样的多层for循环。
伪代码如下：
dfs ()
{
if target == 0
{
保存结果；
返回；
}
for(auto num : candidates)
{
元素存入缓存
dfs()
弹出缓存中最后一个元素，继续
}
}
实现
cpp
class Solution
{
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
vector<vector<int>> ans;
vector<int> res;
dfs(ans, res, candidates, target, 0);
return ans;
}
void dfs(vector<vector<int>> &ans, vector<int> &res, vector<int> &candidates, int target, int index)
{
if (target == 0)
{
ans.push_back(res);
return;
}
if (target < 0)
return;
//
for (int i = index; i < candidates.size(); ++i)
{
res.push_back(candidates[i]);
dfs(ans, res, candidates, target - candidates[i], i); // 不使用i+1，是为了可以重复使用当前的值
res.pop_back();
}
}
};
golang
改编自cpp实现：
var ans [][]int
var res [] int
func combinationSum(candidates []int, target int) [][]int {
ans = make([][]int,0)
res = make([]int,0)
dfs(candidates,target,0)
return ans
}
func dfs(candidates []int,target,index int){
if target == 0{
tmp := make([]int,len(res))
copy(tmp,res)
ans = append(ans,tmp)
return
}
if target < 0{
return
}
for i := index;i<len(candidates);i++{
res = append(res,candidates[i])
dfs(candidates,target-candidates[i],i)
res = res[:len(res)-1]
}
}
声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。