type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个不含重复数字的数组
nums,返回其所有可能的全排列 。可以按任意顺序 返回答案。
示例 1:

示例 2:
示例 3:
提示:
1 <= nums.length <= 6
10 <= nums[i] <= 10
nums中的所有整数 互不相同
解法一:Python 标准库 itertools.permutations
- 直接调用
itertools.permutations(iterable, r=None),生成所有长度为 r 的排列(默认 r = 输入长度,生成全排列)。
- 返回的是一个迭代器,节省内存,调用时转换成列表即可。
解法二:回溯 + visited
把所有排列看作一棵“排列树”。第 k 层表示“第 k 位要放谁”。从根到叶的一条路径就是一个排列。
- 通过递归枚举每个位置可能使用的数字,选择后递归处理下一个位置。
- 维护已使用元素的状态,避免重复选取。
- 每到达递归的叶子节点(排列完成长度),将当前路径加入结果集。
- 通过递归调用栈和回溯(状态重置),完成所有排列的遍历。
时间 :Θ(n·n!)。叶子数就是排列数
n!;每到叶子要拷贝长度 n 到答案 空间:Θ(n),递归深度 +
visited + 路径栈 解法三:“前缀固定” 原地交换
思路:把排列问题看作是逐步确定排列的每一位元素
- 把数组看成两部分:前缀区间
[0..first-1]已经确定的元素,和后缀区间[first..n-1]尚未确定的元素。
- 在当前递归层级,固定前缀不动,将后缀区间的每一个元素依次交换到
first位置,表示选择这个元素作为当前位的元素,生成新的排列前缀。
- 递归下一层,继续确定下一位并往后递归。
- 递归返回时,再交换回去还原数组(即回溯)。
- 这样“原地交换”操作避免额外空间开销,状态由数组本身体现,减少拷贝。
- 利用交换表达“选择”,利用回溯保证不丢失全排列的每一种顺序可能。
- 时间 :Θ(n·n!)
- 空间复杂度:O(n),递归栈最大深度为数组长度n。
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-46-全排列
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 44] 通配符匹配
下一篇
[Leetcode 62] 不同路径