组合-LeetCode

77. 组合 - Combinations

🎯 问题描述（来源于LeetCode）

描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
可以按任意顺序返回答案。

说明：

• 组合中的元素不能重复（每个数字只能使用一次）。
• 顺序不同的相同组合视为同一组合。

示例：

• 示例 1：

输入: n = 4, k = 2
输出: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

• 示例 2：

输入: n = 1, k = 1
输出: [[1]]

💻 解题思路

思路：回溯法（逆序枚举 + 剪枝）

算法步骤

1. 初始化结果列表 ans 和当前路径列表 path。
2. 定义递归函数 dfs(i)，其中 i 表示当前可选的数字上限（从 i 开始向下选择）：
   • 计算剩余需要选的数字个数 d = k - len(path)。
   • 如果 d == 0，说明已选满 k 个数，将 path 的副本加入 ans 并返回。
   • 如果 i > d，则尝试不选当前数字 i：递归 dfs(i-1)（跳过 i）。
   • 然后尝试选当前数字 i：将 i 加入 path，递归 dfs(i-1)，最后回溯弹出 i。
3. 从 dfs(n) 开始搜索。
4. 返回 ans。

代码实现

from typing import List

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

        def dfs(i):
            d = k - len(path)
            if d == 0:
                ans.append(path[:])
                return
            if i > d:
                dfs(i-1)
            
            path.append(i)
            dfs(i-1)
            path.pop()
        
        dfs(n)
        return ans

📊 性能分析

• 时间复杂度：$O(C(n, k) \cdot k)$，其中 $C(n, k)$ 是组合数，每个组合复制到结果需要 $O(k)$ 时间。
• 空间复杂度：$O(k)$，递归栈深度和路径存储。

思考

该解法采用逆序枚举（从 n 向下递归），通过 d = k - len(path) 计算还需选择的数字个数。关键剪枝：当 i > d 时，才尝试不选 i；否则如果 i <= d，则必须选 i，否则剩余数字不够凑齐 k 个。
优点：

• 代码简洁，利用 d 巧妙控制剪枝，减少了不必要的递归分支。
• 无需显式循环，依靠递归顺序自然生成组合。
• 递归树深度固定为 n，但通过剪枝实际访问节点数远小于 $2^n$。

注意事项：

• 递归顺序是先尝试不选，再选，但受剪枝影响，当 i <= d 时不会走不选分支，直接选当前数。
• 由于递归是从大到小，得到的 path 中数字是递减的，但最终结果中顺序无关紧要（可以是任意顺序）。
• 该解法与常规的从小到大枚举（循环从 start 到 n）思路不同，但同样正确且高效。

改进建议：

• 若希望结果按升序输出，可在加入结果前对 path 排序，或改用正向枚举。
• 对于非常大的 n 和 k，此方法依然会指数级增长，但组合数本身限制了输出规模。

该实现是组合问题的经典解法之一，值得学习。