回溯算法#

回溯是一种在决策树中搜索所有可能路径的算法，用于解决组合、排列、子集等问题。

回溯三问#

站在回溯树的一个节点上，需要思考三个核心问题：

路径：已经做出的选择。
选择列表：当前可以做的选择。
结束条件：到达决策树底层，无法再继续选择。

通用代码模板#

1
result = []
2

3
def backtrack(路径, 选择列表):
4
    if 满足结束条件:
5
        result.append(路径[:])
6
        return
7

8
    for 选择 in 选择列表:
9
        做选择
10
        backtrack(路径, 选择列表)
11
        撤销选择

🔁 核心：for 循环里递归调用，递归前“做选择”，递归后“撤销选择”。

组合问题#

从一个集合中选出若干元素的所有组合。
无需考虑元素顺序。
回溯中通常通过控制递归的起始位置避免重复。

77. 组合#

LeetCode 77. 组合

1
class Solution:
2
    def combine(self, n: int, k: int) -> List[List[int]]:
3
        self.res = []        # 存放结果
4
        self.path = []       # 当前组合路径
5
        self.backtrack(n, k, 1)
6
        return self.res
7

8
    def backtrack(self, n, k, start):
9
        # 终止条件：组合长度为 k
10
        if len(self.path) == k:
11
            self.res.append(self.path[:])
12
            return
13
        # 枚举所有可选数值
14
        for i in range(start, n + 1):
15
            self.path.append(i)                  # 做选择
16
            self.backtrack(n, k, i + 1)          # 递归
17
            self.path.pop()                      # 撤销选择

216. 组合总和 III#

LeetCode 216. 组合总和 III

1
class Solution:
2
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
3
        self.path = []       # 当前路径
4
        self.res = []        # 最终结果
5
        self.sum = 0         # 当前路径和
6
        self.backtrack(k, n, 1)
7
        return self.res
8

9
    def backtrack(self, k, n, start):
10
        # 终止条件：长度为 k 且和为 n
11
        if len(self.path) == k and self.sum == n:
12
            self.res.append(self.path[:])
13
            return
14
        # 剪枝：长度超了或者和超了
15
        if len(self.path) >= k or self.sum > n:
16
            return
17
        for i in range(start, 10):  # 数字范围 1~9
18
            if i + self.sum > n:    # 剪枝：当前值已超
19
                break
20
            self.sum += i
21
            self.path.append(i)
22
            self.backtrack(k, n, i + 1)
23
            self.sum -= i
24
            self.path.pop()

17. 电话号码的字母组合#

LeetCode 17. 电话号码的字母组合

1
class Solution:
2
    # 数字到字符的映射
3
    mapping = [
4
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
5
    ]
6

7
    def letterCombinations(self, digits: str) -> List[str]:
8
        self.path = []       # 当前路径
9
        self.res = []        # 存放所有结果
10
        if not digits:
11
            return self.res
12
        self.backtrack(digits, 0)
13
        return self.res
14

15
    def backtrack(self, digits, index):
16
        # 终止条件：路径长度等于输入数字长度
17
        if len(self.path) == len(digits):
18
            self.res.append(''.join(self.path))
19
            return
20

21
        digit = ord(digits[index]) - ord('0')
22
        for char in self.mapping[digit]:
23
            self.path.append(char)               # 做选择
24
            self.backtrack(digits, index + 1)    # 递归
25
            self.path.pop()                      # 撤销选择