0046. 全排列
题目地址(46. 全排列)
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]]前置知识
公司
阿里
腾讯
百度
字节
思路
回溯的基本思路清参考上方的回溯专题。
以 [1,2,3] 为例，我们的逻辑是：
先从 [1,2,3] 选取一个数。
然后继续从 [1,2,3] 选取一个数，并且这个数不能是已经选取过的数。
如何确保这个数不能是已经选取过的数？我们可以直接在已经选取的数字中线性查找，也可以将已经选取的数字中放到 hashset 中，这样就可以在 $O(1)$ 的时间来判断是否已经被选取了，只不过需要额外的空间。
重复这个过程直到选取的数字个数达到了 3。
关键点解析
回溯法
backtrack 解题公式
代码
语言支持: Javascript, Python3,CPP
Javascript Code:
function backtrack(list, tempList, nums) { if (tempList.length === nums.length) return list.push([...tempList]); for (let i = 0; i < nums.length; i++) { if (tempList.includes(nums[i])) continue; tempList.push(nums[i]); backtrack(list, tempList, nums); tempList.pop(); }}/** * @param {number[]} nums * @return {number[][]} */var permute = function (nums) { const list = []; backtrack(list, [], nums); return list;};Python3 Code:
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: """itertools库内置了这个函数""" import itertools return itertools.permutations(nums) def permute2(self, nums: List[int]) -> List[List[int]]: """自己写回溯法""" res = [] def backtrack(nums, pre_list): if len(nums) <= 0: res.append(pre_list) else: for i in nums: # 注意copy一份新的调用，否则无法正常循环 p_list = pre_list.copy() p_list.append(i) left_nums = nums.copy() left_nums.remove(i) backtrack(left_nums, p_list) backtrack(nums, []) return res def permute3(self, nums: List[int]) -> List[List[int]]: """回溯的另一种写法""" res = [] length = len(nums) def backtrack(start=0): if start == length: # nums[:] 返回 nums 的一个副本，指向新的引用，这样后续的操作不会影响已经已知解 res.append(nums[:]) for i in range(start, length): nums[start], nums[i] = nums[i], nums[start] backtrack(start+1) nums[start], nums[i] = nums[i], nums[start] backtrack() return resCPP Code:
class Solution { vector<vector<int>> ans; void dfs(vector<int> &nums, int start) { if (start == nums.size() - 1) { ans.push_back(nums); return; } for (int i = start; i < nums.size(); ++i) { swap(nums[i], nums[start]); dfs(nums, start + 1); swap(nums[i], nums[start]); } }public: vector<vector<int>> permute(vector<int>& nums) { dfs(nums, 0); return ans; }};复杂度分析 令 N 为数组长度。
时间复杂度：$O(N!)$
空间复杂度：$O(N)$
相关题目
最后更新于
这有帮助吗？