LeetCode-216. 组合总和 III - sheep44044的小站

回溯#

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9

每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

** 示例 1:**

1
输入: k = 3, n = 7
2
输出: [[1,2,4]]
3
解释:
4
1 + 2 + 4 = 7
5
没有其他符合的组合了。

示例 2:

1
输入: k = 3, n = 9
2
输出: [[1,2,6], [1,3,5], [2,3,4]]
3
解释:
4
1 + 2 + 6 = 9
5
1 + 3 + 5 = 9
6
2 + 3 + 4 = 9
7
没有其他符合的组合了。

示例 3:

1
输入: k = 4, n = 1
2
输出: []
3
解释: 不存在有效的组合。
4
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

手撕

1
func combinationSum3(k int, n int) [][]int {
2
    res := [][]int{}
3
    path := []int{}
4

5
    var end int
6
    if n > 9 {
7
        end = 9
8
    }else {
9
        end = n
10
    }
11

12
    var sum int
13
    var backtrack func(int)
14
    backtrack = func(index int) {
15
        if len(path) == k {
16
            if sum == n {
17
                res = append(res, append([]int(nil), path...))
18
                return
19
            }
20
            return
21
        }
22

23
        for i := index; i <= end; i++ {
24
            path = append(path, i)
25
            sum += i
26
            backtrack(i+1)
27
            path = path[:len(path)-1]
28
            sum -= i
29
        }
30
    }
31

32
    backtrack(1)
33
    return res
34
}

剪枝优化版

1
func combinationSum3(k int, n int) [][]int {
2
    var res [][]int
3
    var path []int
4
    var sum int
5

6
    var backtrack func(int)
7
    backtrack = func(startIndex int) {
8
        if sum > n {
9
            return
10
        }
11

12
        if len(path) == k {
13
            if sum == n {
14
                res = append(res, append([]int(nil), path...))
15
            }
16
            return
17
        }
18

19
        maxStart := 9 - (k - len(path)) + 1
20

21
        for i := startIndex; i <= maxStart; i++ {
22
            if sum + i > n {
23
                break
24
            }
25

26
            path = append(path, i)
27
            sum += i
28
            backtrack(i + 1)
29
            sum -= i
30
            path = path[:len(path)-1]
31
        }
32
    }
33

34
    backtrack(1)
35
    return res
36
}