leetcode 39. 组合总和

题目描述

给定一个无重复元素的数组 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]
]

题解

递归,遍历数组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
}