难度: 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 <= 201 <= k <= n注意：本题与主站 77 题相同： https://leetcode-cn.com/problems/combinations/
运行时间: 28 ms
内存: 17.4 MB
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
count = []
ans = []
def fun(i):
if n-i + 1 < k - len(ans):
return
if len(ans) == k:
count.append(ans[:])
return
ans.append(i)
fun(i+1)
ans.pop()
fun(i+1)
fun(1)
return count
这个解决方案使用了回溯法来找出所有可能的k个数的组合。首先，定义一个递归函数fun，它从1到n逐个尝试添加数字到当前组合ans中。如果当前组合的长度到达k，就将其复制后添加到结果列表count中。如果组合未完成，函数继续递归尝试当前数字i的下一个数字i+1。此外，函数在尝试每个数字后，都会将其从组合中移除（回溯），然后尝试下一个数字。此解法还包含一个剪枝的优化：如果当前可选的数字数量小于所需的数量，就提前终止递归。
时间复杂度: O(2^n)
空间复杂度: O(n + k)
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
count = [] # 结果列表
ans = [] # 当前组合
def fun(i):
# 剪枝：如果剩余数字不足以填满组合，则终止递归
if n - i + 1 < k - len(ans):
return
# 如果当前组合长度等于k，则复制并添加到结果列表
if len(ans) == k:
count.append(ans[:])
return
# 尝试包含当前数字i
ans.append(i)
fun(i + 1)
# 回溯：移除当前数字并尝试下一个数字
ans.pop()
fun(i + 1)
fun(1)
return count
在递归函数`fun`中的剪枝操作是通过判断剩余可选数字的数量是否足够完成当前组合来实现的。具体来说，如果当前组合`ans`已经包含了一些数字，那么还需要`k - len(ans)`个数字来完成一个有效的组合。如果从当前数字`i`开始到`n`的数字总数（即`n - i + 1`）小于所需的数字数量（`k - len(ans)`），那么即使继续递归，也无法构成一个有效的组合。因此，此时可以提前终止递归，避免无效的计算和递归调用，从而提高算法的效率。
在递归函数`fun`中，第一个递归调用是在将当前数字`i`添加到组合`ans`之后执行的，这意味着正在探索包含数字`i`的所有可能组合。完成这部分递归后，当前数字`i`从组合中被移除（回溯），然后进行第二个递归调用，这次递归不再考虑数字`i`，而是从数字`i+1`开始尝试。这种方法每次递归都是基于不同的起始数字，确保了组合中的数字是按照递增顺序排列，避免了生成重复的组合。例如，组合[1, 2]在回溯后不会再生成[2, 1]，因为我们总是从当前数字的下一个开始递归。
递归的最大深度实际上取决于递归函数调用链中最深的那一层，这通常与数字的范围`n`有关，而不单是组合的大小`k`。在这个特定的问题中，尽管我们是在构建大小为`k`的组合，递归函数`fun`却是从1到`n`逐个尝试每个数字，可能会递归到`n`层深，尤其是在极端情况下，比如当`k`接近`n`时。因此，递归的最大深度是`n`而不仅仅是`k`。