leetcode 39. 组合总和

题解

递归,遍历数组candidates,通过target减去数组中相应的值,不断缩小target进行递归,同时为了避免重复,从数组中取的值不能大于target/2,同时不能小于上一次的取值prev
例如, candidates=[2,3,5,6,7,8,9,11,12]; target = 14,可以递归(2,12),(3,11),(5,9),(6,8),(7,7)

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func combinationSum(candidates []int, target int) [][]int {
return combination(candidates, []int{}, 0, target)
}

func combination(candidates []int, arr []int, prev, target int) [][]int {
res := make([][]int, 0)
if target == 0 {
tmp := append([]int{}, arr...)
res = append(res, tmp)
return res
}
for _, v := range candidates {
if (v <= target/2 && v >= prev) || v == target {
arr = append(arr, v)
res = append(res, combination(candidates, arr, v, target-v)...)
arr = arr[:len(arr)-1]
}
}
return res
}