从1-n几个数字中选出m个数字组合,输出所有组合方式
时间: 2023-06-13 10:05:30 浏览: 122
这个问题可以用回溯法来解决。回溯法是一种通过穷举所有可能的候选解来找出所有的解的算法。具体来说,在回溯法中,我们首先选择一个候选解,然后递归地搜索剩余的候选解,直到找到所有的解或者确定不存在解为止。
下面是一个使用回溯法来解决这个问题的 Python 代码实现:
```python
def combinations(n, m):
def backtrack(start, path):
if len(path) == m:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
backtrack(i+1, path)
path.pop()
res = []
backtrack(1, [])
return res
```
这个函数的输入是两个整数 `n` 和 `m`,表示在 1 到 `n` 之间选出 `m` 个数字组合。函数的输出是一个列表,包含所有可能的组合方式。函数中使用了一个内部函数 `backtrack`,它负责递归地搜索候选解。在搜索过程中,我们维护了一个 `path` 列表,它存储了当前已选的数字。如果 `path` 的长度等于 `m`,那么就将 `path` 添加到结果列表 `res` 中。否则,我们从 `start` 开始枚举所有可能的数字,并将其添加到 `path` 中,然后递归地搜索剩余的数字。搜索完成后,需要将 `path` 中最后添加的数字弹出,以便进行下一次搜索。
下面是一个例子,演示了如何使用 `combinations` 函数来输出所有可能的组合方式:
```python
>>> combinations(4, 2)
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> combinations(5, 3)
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
```
在这个例子中,`combinations(4, 2)` 输出了 1 到 4 中选出 2 个数字的所有组合方式,`combinations(5, 3)` 输出了 1 到 5 中选出 3 个数字的所有组合方式。