组合

难度: Medium

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

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

示例 2：

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

提示：

1 <= n <= 20
1 <= k <= n

Submission

运行时间: 416 ms

内存: 16.2 MB

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        nums = list(range(1, n+1))

        def backtrack(path, start):
            if len(path) == k:
                result.append(list(path))
                return
            
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(path, i+1)
                path.pop()
        
        backtrack([], 0)
        return result

Explain

这个题解使用了回溯算法。它从数字1开始，通过递归的方式枚举所有可能的组合。在递归函数中，如果当前路径的长度等于k，就将当前路径加入结果列表中。否则，从当前位置开始，依次将每个数字加入路径，并递归调用函数，直到找到所有的组合。在回溯过程中，需要将最后加入的数字从路径中移除，以便尝试其他的组合。

时间复杂度: O(k * n^k)

空间复杂度: O(k * C(n, k))

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        nums = list(range(1, n+1))

        def backtrack(path, start):
            # 如果当前路径的长度等于k，将当前路径加入结果列表中
            if len(path) == k:
                result.append(list(path))
                return
            
            # 从当前位置开始，依次将每个数字加入路径
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(path, i+1)
                # 回溯，将最后加入的数字从路径中移除
                path.pop()
        
        backtrack([], 0)
        return result

Explore

回溯算法适用于解决决策树的遍历问题，特别是当问题需要探索所有可能的解决方案时。在组合问题中，我们需要找到所有可能的组合方式，这正是构建决策树并遍历所有可能路径的典型场景。回溯算法通过试探和回退的策略，能够有效地找到所有可能的组合，而且在发现某条路径不可能成为解时能够及时回退，减少无效计算。其他算法如动态规划或贪心算法不适合这类问题，因为它们更适合于找到最优解而不是列举所有可能的解。

从`start`索引开始循环而不是从0开始，是为了避免生成重复的组合并保证组合内的元素是升序的。如果从0开始，将会重复考虑之前已经选择过的数字，导致生成如[1,2]和[2,1]这样重复的组合。使用`start`参数确保每次添加到组合中的数字都是之前数字的后续，这样自然保持了组合内数字的顺序，简化了问题处理过程，并且减少了无效的组合尝试。

`path`参数用于记录当前的组合路径，它是一个动态变化的列表，用于存储已选择的元素。每次递归调用都可能向path中添加新的元素或从中移除元素。`start`参数用于控制下一次添加到组合中的元素的起始位置，以防止重复选择同一个元素，并确保组合中的元素顺序。这两个参数是实现回溯逻辑的关键，使得算法能够正确地递归遍历所有可能的组合。

`path.pop()`操作是回溯过程中的关键步骤，用于撤销上一步做出的选择，从而探索其他可能的选择。当一条路径被完全探索后（即达到递归的终点），需要回退到上一状态以探索其他分支的可能性。这种操作确保了每个可能的组合都可以被正确枚举，并且使得递归函数能够重复利用`path`变量，节省空间复杂度。