77. 组合

77. 组合
要生成给定范围 [1, n] 中所有可能的 k 个数的组合，可以使用递归和回溯的方法。以下是详细的代码及注释：

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []  # 用于存储所有组合结果
        
        def backtrack(start: int, path: List[int]):
            # 如果当前路径长度为 k，则将其加入结果
            if len(path) == k:
                result.append(path[:])
                return
            
            # 从 start 开始遍历到 n
            for i in range(start, n + 1):
                # 将当前数字加入路径
                path.append(i)
                # 递归调用，继续生成组合，起始数字变为 i + 1
                backtrack(i + 1, path)
                # 回溯，移除路径中的最后一个数字
                path.pop()
        
        # 从 1 开始生成组合
        backtrack(1, [])
        return result

详细中文注释

1. 导入必要的库：

   from typing import List
   

   • List 用于类型注解，表示返回的结果是一个包含列表的列表。

2. 定义解决方案类 Solution 及其方法 combine：

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

3. 初始化用于存储所有组合结果的变量 result：

   result = []
   

4. 定义辅助递归函数 backtrack：

   def backtrack(start: int, path: List[int]):
   

   • start 表示当前递归的起始数字。
   • path 表示当前组合的路径。

5. 判断当前路径长度是否为 k：

   if len(path) == k:
       result.append(path[:])
       return
   

   • 如果当前路径长度等于 k，将路径的副本加入结果中，并返回。

6. 从 start 开始遍历到 n：

   for i in range(start, n + 1):
       path.append(i)
       backtrack(i + 1, path)
       path.pop()
   

   • 遍历从 start 到 n 的数字。
   • 将当前数字加入路径中。
   • 递归调用 backtrack 函数，起始数字变为 i + 1。
   • 回溯，将路径中的最后一个数字移除。

7. 开始递归生成组合：

   backtrack(1, [])
   

8. 返回所有组合结果：

   return result
   

示例

假设 n = 4，k = 2，则调用 combine 函数将生成以下所有组合：

[
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 3],
  [2, 4],
  [3, 4]
]

通过这种递归和回溯的方法，可以有效地生成范围 [1, n] 中所有可能的 k 个数的组合。