Leetcode-Medium 46. Permutations
Leetcode-Medium 46. Permutations
致Great
发布于 2019-03-11 10:35:15
发布于 2019-03-11 10:35:15
题目描述
给出一组数字，输出全排列的结果
例子：
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]思路
回溯法|递归|DFS 关于回溯法的讲解，推荐一篇好文章# Backtracking回溯法(又称DFS,递归)全解
用爬山来比喻回溯，好比从山脚下找一条爬上山顶的路,起初有好几条道可走,当选择一条道走到某处时,又有几条岔道可供选择,只能选择其中一条道往前走,若能这样子顺利爬上山顶则罢了,否则走到一条绝路上时或者这条路上有一坨屎,我们只好返回到最近的一个路口,重新选择另一条没走过的道往前走。如果该路口的所有路都走不通,只得从该路口继续回返。照此规则走下去,要么找到一条到达山顶的路,要么最终试过所有可能的道,无法到达山顶。 回溯本质上是一种穷举。
还有一些爱混淆的概念：递归，回溯，DFS。这些都是一个事儿的不同方面。以下以回溯统称，因为这个词听上去很文雅。
对于一个数组[a1,a2,a3],那么它的全排列为： Permute([a1,a2,a3])=[取出的某一个数]+Permute([a1,a2,a3]-取出的某一个数) 如果我们要用1,2,3进行排列，我们可以先抽出一个元素，比如我们现在抽出1，那么我们下面要做的事就是使用2,3两个元素构造排列
代码实现
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
lev, avail, lev_node = 0, nums, []
N = len(nums)
def dfs(lev, avail, lev_node):
if lev == N:
res.append(lev_node)
return
for i in range(len(avail)):
dfs(lev+1, avail[:i]+avail[i+1:], lev_node+[avail[i]])
dfs(lev, avail, lev_node)
return(res)或者
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res=[]
def helper(res,l,r,n,max):
if n==max:
print l
res.append(l)
for i in range(0,len(r)):
helper(res,l+[r[i]],r[:i]+r[i+1:],n+1,max)
helper(res,[],nums,0,len(nums))
return res参考资料
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.02.26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录