题目描述
给出一组数字，输出全排列的结果
例子：
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
