LeetCode 题解工作台
全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入： nums = [1,2,3] 输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入： nums = [0,1…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们设计一个函数 表示已经填完了前 个位置，现在需要填第 个位置。枚举所有可能的数，如果这个数没有被填过，就填入这个数，然后继续填下一个位置，直到填完所有的位置。 时间复杂度 $O(n \times n!)$，其中 是数组的长度。一共有 个排列，每个排列需要 的时间来构造。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
解题思路
方法一：DFS（回溯）
我们设计一个函数 表示已经填完了前 个位置，现在需要填第 个位置。枚举所有可能的数，如果这个数没有被填过，就填入这个数，然后继续填下一个位置，直到填完所有的位置。
时间复杂度 ，其中 是数组的长度。一共有 个排列，每个排列需要 的时间来构造。
相似题目：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i >= n:
ans.append(t[:])
return
for j, x in enumerate(nums):
if not vis[j]:
vis[j] = True
t[i] = x
dfs(i + 1)
vis[j] = False
n = len(nums)
vis = [False] * n
t = [0] * n
ans = []
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n! * n) due to generating n! permutations and copying them into the result. Space complexity is O(n) for recursion depth and O(n) for used markers or swaps. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate immediately considers backtracking and marks elements used for recursion.
- question_mark
Candidate identifies recursion depth and correctly restores state during backtracking.
- question_mark
Candidate demonstrates understanding of how to prune or skip redundant recursion paths.
常见陷阱
外企场景- error
Failing to restore element state after recursive calls leads to incorrect permutations.
- error
Ignoring the need for a 'used' marker or proper swap tracking can cause duplicates or missing permutations.
- error
Not handling recursion base cases correctly, especially when building the final permutation list.
进阶变体
外企场景- arrow_right_alt
Generate permutations of a string of distinct characters instead of integers.
- arrow_right_alt
Generate k-length permutations from n elements instead of full-length permutations.
- arrow_right_alt
Generate permutations allowing duplicate elements and remove duplicates from the result list.