给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你需要按顺序返回答案。 提示: 1 <= n <= 20 1 <= k <= n 输入 两个整数 n 和 k 输出 范围 [1, n] 中所有可能的 k 个数的组合
时间: 2024-02-21 19:59:30 浏览: 23
以下是一个 Python 代码实现,用于生成给定范围内所有可能的 k 个数的组合:
```python
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
self.dfs(n, k, 1, [], res)
return res
def dfs(self, n, k, start, path, res):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
self.dfs(n, k, i+1, path, res)
path.pop()
```
这个解法使用了深度优先搜索算法。主要思路是遍历 1 到 n 中的每个数字,将其加入当前的组合中,并递归搜索剩下的数字中的组合。如果已经选满了 k 个数字,就将当前组合添加到结果列表中。如果当前数字已经大于 n,或者当前组合已经有了 k 个数字,就返回上一层递归。
代码中 `dfs()` 方法接受四个参数:n 表示数字的范围,k 表示需要选多少个数字,start 表示从哪个数字开始选,path 表示当前已经选了哪些数字。在主函数中,代码首先创建一个空列表 res 用于存储结果,在调用 `dfs()` 方法开始搜索,最后返回得到的结果列表。
需要注意的是,为了避免重复,我们在递归时,下一个数字的起始点应该是当前数字的下一个数,即 `start+1`。