代码随想录算法训练营第二十一天 | 77、216、17

算法
, , ,

77. 组合

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
package main

func combine(n int, k int) [][]int {
    var result [][]int
    var path []int

    var backtrack func(int)
    backtrack = func(start int) {
        // 当路径长度等于 k 时，将当前路径加入结果集
        if len(path) == k {
            temp := make([]int, k)
            copy(temp, path)
            result = append(result, temp)
            return
        }

        // 遍历当前可选的数字范围
        for i := start; i <= n; i++ {
            // 剪枝：剩余可用数字不足时提前终止循环
            remaining := k - len(path)
            if n-i+1 < remaining {
                break
            }

            path = append(path, i)    // 选择当前数字
            backtrack(i + 1)          // 递归处理下一层（从下一个数字开始）
            path = path[:len(path)-1] // 撤销选择，回溯到上一步
        }
    }

    backtrack(1) // 从数字 1 开始生成组合
    return result
}

216. 组合总和 III

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
36
37
38
package main

func combinationSum3(k int, n int) [][]int {
    var result [][]int
    var path []int

    var backtrack func(int, int)
    backtrack = func(start, sum int) {
        // 当路径长度达到 k 时，检查 sum 是否等于 n
        if len(path) == k {
            if sum == n {
                tmp := make([]int, k)
                copy(tmp, path)
                result = append(result, tmp)
            }
            return
        }

        remaining := k - len(path) // 还需选择的数字个数
        maxStart := 10 - remaining // 最大起始值（剪枝关键）

        for i := start; i <= maxStart; i++ {
            // 剪枝条件 1：当前 sum 加 i 已超过目标值
            // 剪枝条件 2：maxStart 自动保证剩余数字数量足够
            if sum+i > n {
                break
            }

            path = append(path, i)
            backtrack(i+1, sum+i)     // 递归处理下一层（从 i+1 开始）
            path = path[:len(path)-1] // 回溯
        }
    }

    backtrack(1, 0)
    return result
}

17. 电话号码的字母组合

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
36
37
38
39
40
41
42
43
44
45
46
47
48
package main

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    // 建立数字到字母的映射表
    digitMap := map[byte]string{
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
    }

    var result []string
    var backtrack func(int, []byte)

    // 回溯函数定义
    backtrack = func(index int, path []byte) {
        // 当路径长度等于输入数字长度时，保存结果
        if index == len(digits) {
            result = append(result, string(path))
            return
        }

        // 获取当前数字对应的字母集合
        letters := digitMap[digits[index]]
        // 遍历所有可能的字母选择
        for _, char := range letters {
            // 做出选择：将当前字母加入路径
            path = append(path, byte(char))
            // 递归处理下一个数字
            backtrack(index+1, path)
            // 撤销选择：回溯到上一步状态
            path = path[:len(path)-1]
        }
    }

    // 从第一个数字开始回溯
    backtrack(0, []byte{})
    return result
}