[Medium]LeetCode#40. 组合总和 II
题目原地址
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
1
2
3
4
5
6
| [
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
|
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
基本算法，求除本身外剩余数的组合是否等于target - 本身，在原基础上改造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
return dfs2(candidates, target)
}
func dfs2(candidates []int, target int) [][]int {
l := len(candidates)
if l == 0 {
return nil
}
var res [][]int
next := target - candidates[0] // 下一个和
switch {
case next < 0:
return nil
case next == 0:
return [][]int{{candidates[0]}}
case next > 0: // 寻找子和的任意组合
combines := dfs2(candidates[1:], next)
for _, combine := range combines {
res = append(res, append(combine, candidates[0])) // 将子和的任意组合添加到解中
}
}
s := 1
for i := 1; i < l; i++ {
if candidates[i] == candidates[0] {
s = i+1
} else {
break
}
}
res = append(res, dfs2(candidates[s:], target)...) // 在后续数组中尝试和为 target 的组合
return res
}
|
执拗前行