[Medium]LeetCode#39. 组合总和
题目原地址
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
1
2
3
4
5
| [
[2,2,2,2],
[2,3,3],
[3,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
| func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
return dfs(candidates, target)
}
func dfs(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 := dfs(candidates, next)
for _, combine := range combines {
res = append(res, append(combine, candidates[0])) // 将子和的任意组合添加到解中
}
}
res = append(res, dfs(candidates[1:], target)...)// 在后续数组中尝试和为 target 的组合
return res
}
|
执拗前行