77.组合问题

主函数 combine

def combine(self, n: int, k: int) -> List[List[int]]:result = []  # 存放所有有效的组合self.backtracking(n, k, 1, [], result)  # 从数字1开始搜索return result

• 作用：初始化并启动回溯过程。
• 参数：
  • n=4：数字范围是1到4。
  • k=2：每个组合需要2个数字。
• 过程：
  1. 创建空列表 result 存储结果。
  2. 调用 backtracking 开始递归搜索。

回溯函数 backtracking

def backtracking(self, n, k, startIndex, path, result):if len(path) == k:          # 终止条件：当前组合已选够k个数result.append(path[:])   # 将当前组合存入结果returnfor i in range(startIndex, n + 1):  # 遍历可选数字path.append(i)           # 选择当前数字iself.backtracking(n, k, i + 1, path, result)  # 递归处理下一个数字path.pop()               # 回溯：撤销选择i

具体执行步骤（以 n=4, k=2 为例）

1. 主函数调用 backtracking(4, 2, 1, [], result)

• startIndex = 1, path = []
• 进入循环 for i in range(1, 5):

  • i = 1:

    • path.append(1) → path = [1]
    • 递归调用 backtracking(4, 2, 2, [1], result):
      • startIndex = 2, path = [1]
      • 子循环 for i in range(2, 5):
        • i = 2:
          • path.append(2) → path = [1, 2]

          • path = [1]
            path.append(2)       # path = [1,2]
            # 现在调用 backtracking(n,k,3,[1,2],result)
            # ↓ 进入新的递归层级
            if len([1,2]) == 2:  # 立刻触发检查！result.append([1,2])return           # 直接返回，不会继续后面的循环
            # 回到上一层
            path.pop()          # path恢复为[1]

            对下面的解释

          • 满足 len(path) == 2:
            • result.append([1, 2]) → result = [[1, 2]]
          • path.pop() → path = [1] （回溯）
        • i = 3:
          • path.append(3) → path = [1, 3]
          • 满足 len(path) == 2:
            • result.append([1, 3]) → result = [[1, 2], [1, 3]]
          • path.pop() → path = [1] （回溯）
        • i = 4:
          • path.append(4) → path = [1, 4]
          • 满足 len(path) == 2:
            • result.append([1, 4]) → result = [[1, 2], [1, 3], [1, 4]]
          • path.pop() → path = [1] （回溯）
      • 子递归结束，返回上一层。
    • path.pop() → path = [] （回溯）

  • i = 2:

    • path.append(2) → path = [2]
    • 递归调用 backtracking(4, 2, 3, [2], result):
      • startIndex = 3, path = [2]
      • 子循环 for i in range(3, 5):
        • i = 3:
          • path.append(3) → path = [2, 3]
          • 满足 len(path) == 2:
            • result.append([2, 3]) → result = [[1, 2], [1, 3], [1, 4], [2, 3]]
          • path.pop() → path = [2] （回溯）
        • i = 4:
          • path.append(4) → path = [2, 4]
          • 满足 len(path) == 2:
            • result.append([2, 4]) → result = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4]]
          • path.pop() → path = [2] （回溯）
      • 子递归结束，返回上一层。
    • path.pop() → path = [] （回溯）

  • i = 3:

    • path.append(3) → path = [3]
    • 递归调用 backtracking(4, 2, 4, [3], result):
      • startIndex = 4, path = [3]
      • 子循环 for i in range(4, 5):
        • i = 4:
          • path.append(4) → path = [3, 4]
          • 满足 len(path) == 2:
            • result.append([3, 4]) → result = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
          • path.pop() → path = [3] （回溯）
      • 子递归结束，返回上一层。
    • path.pop() → path = [] （回溯）

  • i = 4:

    • path.append(4) → path = [4]
    • 递归调用 backtracking(4, 2, 5, [4], result):
      • startIndex = 5 > n = 4，直接返回，不处理。
    • path.pop() → path = [] （回溯）