题目描述

给定一个候选人编号的集合 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

解题思路

基本想法还是回溯算法。可以通过递归的方式来尝试每一个数字，看看能否找到满足条件的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func combinationSum2(candidates []int, target int) [][]int {
	ans := [][]int{}
	tmp := []int{}
	var combination func(idx, rest int)
	combination = func(idx, rest int) {
		if rest == 0 {
			ans = append(ans, make([]int, len(tmp)))
			copy(ans[len(ans)-1], tmp)
			return
		}

		for i := idx; i < len(candidates); i++ {
			if x := rest - candidates[i]; x >= 0 {
				tmp = append(tmp, candidates[i])
				combination(i+1, x)
				tmp = tmp[:len(tmp)-1]
			}
            // 这里不能再调用 combination(i+1, x) 了，否则会和 for 的 i++ 后发生的计算过程重复
		}
	}
	combination(0, target)

	return ans
}

上面的代码是没办法通过的，因为它没有处理重复的组合。而如果要在递归过程中跳过重复的数字，那就需要对 candidates 进行排序，并在递归中添加判断来跳过重复的数字。

这里又由于数据范围的限制 1 <= candidates[i] <= 50 和 1 <= target <= 30 ，所以可以参照桶排序的思路来优化。

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
func combinationSum2(candidates []int, target int) [][]int {
	candidatesCnt := make([]int, 31)
	for _, num := range candidates {
		if num <= 30 {
			candidatesCnt[num]++
		}
	}

	tmp := []int{}
	ans := [][]int{}
	var combination func(idx, rest int)
	combination = func(idx, rest int) {
		if rest == 0 {
			ans = append(ans, make([]int, len(tmp)))
			copy(ans[len(ans)-1], tmp)
		}

		for i := idx; i < 31; i++ {
			j := 0
			for x := rest - i; j < candidatesCnt[i] && x >= 0; j, x = j+1, x-i {
				tmp = append(tmp, i)
				combination(i+1, x)
			}
			tmp = tmp[:len(tmp)-j]
		}
	}
	combination(0, target)

	return ans
}

上面的代码是通过数组 candidatesCnt 的下标来表示数字，数组的值表示该数字在 candidates 中出现的次数。如果数字超过 30，则不考虑它，因为 target 的最大值为 30。

而如果数据范围很大，不适用桶排法的话，就可以考虑使用二维数组来存储每个数字的出现次数。

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
35
func combinationSum2(candidates []int, target int) [][]int {
	candidatesCnt := make([][]int, 0, len(candidates))
	sort.Ints(candidates)
	for _, num := range candidates {
		if len(candidatesCnt) == 0 || candidatesCnt[len(candidatesCnt)-1][0] != num {
			candidatesCnt = append(candidatesCnt, []int{num, 1})
		} else {
			candidatesCnt[len(candidatesCnt)-1][1]++
		}
	}

	tmp := []int{}
	ans := [][]int{}
	var combination func(idx, rest int)

	combination = func(idx, rest int) {
		if rest == 0 {
			ans = append(ans, make([]int, len(tmp)))
			copy(ans[len(ans)-1], tmp)
			return
		}
		for i := idx; i < len(candidatesCnt); i++ {
			num, cnt := candidatesCnt[i][0], candidatesCnt[i][1]
			j := 0
			for x := rest - num; j < cnt && x >= 0; j, x = j+1, x-num {
				tmp = append(tmp, num)
				combination(i+1, x)
			}
			tmp = tmp[:len(tmp)-j]
		}
	}
	combination(0, target)

	return ans
}

总结

本题主要考察回溯算法的应用。通过对候选数组的排序和去重处理，可以有效地避免重复组合的产生。在实现过程中，使用了递归函数来尝试每一种可能的组合，并在找到满足条件的组合时将其记录下来。