1、题目描述

https://leetcode-cn.com/problems/permutations/

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

2、代码详解

进阶题：回溯、剪枝-LeetCode47. 全排列 II（可重复数字） https://blog.csdn.net/IOT_victor/article/details/107073704

更简洁的代码（推荐！便于拓展，思路与下面的一样）

class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # nums 选择列表，depth深度， path 路径，used 标记数组！，res 结果 def dfs(nums, size, depth, path, used, res): # 结束条件：nums 中的元素全都在 path 中出现 if depth == size: res.append(path[:]) # 需要传递下path的拷贝，否则对path的修改会影响到结果 return for i in range(size): # used[i]==False，表示未被用过 if not used[i]: # 做选择 used[i] = True path.append(nums[i]) # 进入下一层决策树 dfs(nums, size, depth + 1, path, used, res) # 撤销选择 used[i] = False path.pop() size = len(nums) if len(nums) == 0: return [] used = [False for _ in range(size)] res = [] dfs(nums, size, 0, [], used, res) return res nums = [1,2,3] s = Solution() print(s.permute(nums))

https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

另一种写法

回溯法模板 https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/

回溯算法的框架如下，核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # nums 选择列表， track 路径 def trackBack(nums, track): # 结束条件：nums 中的元素全都在 track 中出现 if len(track) == len(nums): res.append(track[:]) # 需要传递下track的拷贝，否则对track的修改会影响到结果 return for i in nums: # 排除不合法的选择 if i in track: continue # 结束当前循环进入下一循环 # 做选择 track.append(i) # 进入下一层决策树 trackBack(nums, track) # 撤销选择 track.pop() res = [] track = [] # 路径 trackBack(nums, track) return res nums = [1,2,3] s = Solution() print(s.permute(nums))

时间复杂度：O(n ∗ n!)，其中 n 为序列的长度

空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)