[Leetcode 46] 全排列

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个不含重复数字的数组 nums,返回其所有可能的全排列 。
可以按任意顺序 返回答案。
 
示例 1:
notion image
示例 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。
 
 
上一篇
[Leetcode 44] 通配符匹配
下一篇
[Leetcode 62] 不同路径