回溯法 有n个数,输出其中r(r<=n)个数的所有组合代码
时间: 2023-08-31 18:37:08 浏览: 75
### 回答1:
以下是使用回溯法输出n个数中r个数的所有组合的代码实现:
```python
def combinations(n, r):
"""
:param n: 总共n个数
:param r: 选择r个数
"""
if n < r:
return []
def backtrack(first=1, curr=[]):
if len(curr) == r:
res.append(curr[:])
return
for i in range(first, n + 1):
curr.append(i)
backtrack(i + 1, curr)
curr.pop()
res = []
backtrack()
return res
```
使用示例:
```python
combinations(4, 2) # 输出 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
```
该代码的思路是:从第一个数开始,依次尝试选择第二个、第三个……直到第r个数。如果已经选择了r个数,则将当前组合加入结果列表中。否则,继续选择下一个数,直到所有可能的组合都被尝试过为止。
### 回答2:
回溯法是一种通过递归和回溯的方式,用于解决组合问题。对于给定的n个数,输出其中r(r<=n)个数的所有组合,可以使用回溯法的思想来实现。
以下是一个示例的代码实现:
```python
def backtrack(nums, r, temp, result, start):
if len(temp) == r:
result.append(temp[:])
return
for i in range(start, len(nums)):
temp.append(nums[i])
backtrack(nums, r, temp, result, i + 1)
temp.pop()
def combination(nums, r):
result = []
temp = []
backtrack(nums, r, temp, result, 0)
return result
n = int(input("请输入n的值:"))
nums = []
for i in range(n):
num = int(input("请输入第%d个数:" % (i + 1)))
nums.append(num)
r = int(input("请输入r的值(r <= n):"))
combinations = combination(nums, r)
print("所有的组合为:")
for c in combinations:
print(c)
```
使用以上代码,可以实现从给定的n个数中找到r个数的所有组合。输入n、每个数的值以及r的值后,程序会输出所有可能的组合。
需要注意的是,此代码是一个Python示例,可以根据实际情况进行适当的修改和调整。同时,这只是其中一种实现方式,还可以有其他的变体和优化方法。
阅读全文