给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5]
, target =8
, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
题解:
回溯法:
func combinationSum2(candidates []int, target int) [][]int {
var path []int
var result [][]int
var backtracking func(candidates []int, target, sum, startIndex int)
backtracking = func(candidates []int, target, sum, startIndex int) {
// 终止条件
if sum > target {
return
}
if sum == target {
tmp := make([]int, len(path))
copy(tmp, path)
result = append(result, tmp)
return
}
for i := startIndex; i < len(candidates); i++ {
// 剪枝优化
if candidates[i] > target {
break
}
// 去重复
if i > startIndex && candidates[i] == candidates[i-1] {
continue
}
path = append(path, candidates[i])
sum += candidates[i]
backtracking(candidates, target, sum, i+1)
// 回溯
sum -= candidates[i]
path = path[:len(path)-1]
}
}
sort.Ints(candidates)
backtracking(candidates, target, 0, 0)
return result
}
评论前必须登录!
注册