给定一个无重复元素的数组 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]
]
方法:搜索回溯
//一个dfs里面调用2个dfs函数,这样的递归形成了一个类似树的结构
func combinationSum(candidates []int, target int) (ans [][]int) {
comb := []int{}
var dfs func(target, idx int)
dfs = func(target, idx int) {
//idx表示遍历到的下标
if idx == len(candidates) {
return
}
if target == 0 {
//已找到组合,go二维数组append
ans = append(ans, append([]int(nil), comb...))
return
}
// 直接跳过
dfs(target, idx+1)
// 选择当前数
if target-candidates[idx] >= 0 {
comb = append(comb, candidates[idx])
dfs(target-candidates[idx], idx)
comb = comb[:len(comb)-1]
}
}
dfs(target, 0)
return
}
一个dfs里面调用2个dfs函数,这样的递归形成了一个类似树的结构,这个递归注意终止条件,每个数可以选也可以不选,因为数组里面的元素可以重复使用。力扣上的图很详细的表现了过程。
说明:图片和代码均来自于力扣
参考地址:https://leetcode-cn.com/problems/combination-sum/solution/zu-he-zong-he-by-leetcode-solution/