代码随想录｜Day21｜回溯01｜77.组合

77.组合

组合问题不考虑顺序，例如 [1, 2] 和 [2, 1] 是同一个组合。其中 n 为取数的范围，每个组合包含 k个 元素数量，所以我们嵌套 k 个 for循环 可以很容易写出暴力解法。但如果 k 的值过大，代码将会非常冗长。

我们考虑回溯，可以将组合问题看作一棵树，n 为树的宽度，k 为树的深度，回溯的本质依然是暴力解法，只是不需要显式写出嵌套循环而已，而是用递归代替。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 递归参数 start，起始元素
        # 见上图，由于是组合问题，不能选择之前选择过的元素
        # 否则会导致重复
        def backtrack(start, path):
            # 递归终止限制条件：长度满足，遍历到叶子结点
            if len(path) == k:
                # 注意，这里要创建浅拷贝
                # 否则接下来对 path 的修改将会影响到已经存在 result 中的path
                result.append(path[:])
                return
            # 此循环确保遍历所有的 n，遍历宽度
            for num in range(start, n + 1):
                # 对于每一个 n，递归向下遍历，遍历深度
                path.append(num)
                backtrack(num + 1, path)
                path.pop()

        result = []
        backtrack(start = 1, path = [])
        return result

 剪枝：既然已知 k，那么在元素不足以凑齐 k个 的情况下直接剪枝。具体的操作很简单，只需要修改递归终止条件即可。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        def backtrack(start, path):

            if len(path) == k:

                result.append(path[:])
                return
            # 剪枝
            # 从当前的 start 开始，到 n 结束，剩余的数字必须足够构成长为 k 的组合
            # k - len(path)：当前组合还需要的元素数量
            # n - (k - len(path)) + 1 为最远需要的数字
            # + 1：range不含尾
            for num in range(start, n - (k - len(path)) + 1 + 1):

                path.append(num)
                backtrack(num + 1, path)
                path.pop()

        result = []
        backtrack(start = 1, path = [])
        return result