使用dfs写排列组合函数
时间: 2024-05-03 19:22:19 浏览: 8
以下是使用深度优先搜索(DFS)算法实现的排列组合函数:
```
def permute(nums):
"""
返回给定列表的所有排列组合
"""
def dfs(nums, path, res):
if not nums:
res.append(path)
return
for i in range(len(nums)):
dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
res = []
dfs(nums, [], res)
return res
def combine(n, k):
"""
返回从1到n中选取k个数字的所有组合
"""
def dfs(start, k, n, path, res):
if k == 0:
res.append(path)
return
for i in range(start, n+1):
dfs(i+1, k-1, n, path+[i], res)
res = []
dfs(1, k, n, [], res)
return res
```
函数`permute`接受一个列表,返回该列表的所有排列组合。函数`combine`接受两个整数n和k,返回从1到n中选取k个数字的所有组合。在这两个函数中,我们使用了DFS算法,遍历所有可能的情况,并且将所有符合要求的结果存储在一个列表中返回。