全排列
Permutations
本机进度仅保存在当前浏览器
题目描述
给定一个不含重复数字的数组 nums，返回其所有可能的全排列，顺序任意。
示例：nums = [1, 2, 3]，输出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。
解题思路
- 排列与子集的区别：排列关心顺序，每一层都可以从"所有未使用"的元素中选，而非只从 start 之后选。
- 用 used 数组标记已选元素，回溯时先标记、递归、再撤销，保证路径可复用。
- 路径长度达到 n 即收集答案；时间被结果数量 2 界定在 O(n · n!)。
参考实现
查看参考实现Python · 建议先自行作答
def permute(nums):
res, path = [], []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack()
path.pop()
used[i] = False
backtrack()
return res