Links

0046. 全排列

题目地址(46. 全排列)

题目描述

给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [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 res
CPP 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)$

相关题目