如何用回溯法生成全排列？｜腾讯算法面经解析

60 秒回答模板

可以这样回答：用回溯生成全排列，维护当前路径 path 和 used 标记。每一层选择一个未使用元素加入路径，递归到长度为 n 时收集一个排列，然后撤销选择继续尝试。模板是 choose -> recurse -> unchoose。若数组有重复元素，先排序，并在同层跳过 nums[i] === nums[i-1] 且前一个未使用的分支，避免重复排列。全排列数量是 n!，每个排列长度 n，总时间 O(n*n!)，结果空间也很大。swap 原地回溯能减少 used 数组，但重复去重更要小心。要说明空数组、重复元素、输出顺序、递归深度和结果规模爆炸。不要把全排列讲成随机排列或采样题，主线始终是路径选择、递归和撤销选择。验证时重点看：用 [1,2,3] 和 [1,1,2] 验证数量、去重和回溯撤销是否正确。

考点 考点边界

主线 核心机制

易错点 把全排列回溯讲成随机排列或采样题，偏离路径选择、递归和…

深入解析

考点边界

这题必须围绕“回溯生成全排列”本身回答，不能套相邻大类模板。先给定义或目标，再展开机制、边界、取舍和验证抓手。回答时要主动点出题面关键词对应的对象、输入输出和约束条件，避免把具体问题讲成宽泛复习提纲。本题对应“回溯生成全排列”，核心前提是：用回溯生成全排列，维护当前路径 path 和 used 标记。每一层选择一个未使用元素加入路径，递归到长度为 n 时收集一个排列，然后撤销选择继续尝试。

核心机制

模板是 choose -> recurse -> unchoose。若数组有重复元素，先排序，并在同层跳过 nums[i] === nums[i-1] 且前一个未使用的分支，避免重复排列。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

全排列数量是 n!，每个排列长度 n，总时间 O(n*n!)，结果空间也很大。swap 原地回溯能减少 used 数组，但重复去重更要小心。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

要说明空数组、重复元素、输出顺序、递归深度和结果规模爆炸。不要把全排列讲成随机排列或采样题，主线始终是路径选择、递归和撤销选择。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：用 [1,2,3] 和 [1,1,2] 验证数量、去重和回溯撤销是否正确。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

把全排列回溯讲成随机排列或采样题，偏离路径选择、递归和撤销选择的主线。
有重复元素时只在结果层用 Set 去重，没有在同一递归层剪枝，复杂度会被重复分支放大。
只背“回溯生成全排列”的结论，漏掉关键步骤：模板是 choose -> recurse -> unchoose。若数组有重复元素，先排序，并在同层跳过 nums[i] === nums[i-1] 且前一个未使用的分支，避免重复排列。
没有说明“回溯生成全排列”的失败边界：要说明空数组、重复元素、输出顺序、递归深度和结果规模爆炸。不要把全排列讲成随机排列或采样题，主线始终是路径选择、递归和撤销选择。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

全排列回溯为什么需要 used 数组或交换位置？

每一层要保证同一个元素不能被重复选入当前路径。used 数组记录哪些下标已进入路径；交换法则固定当前位置，再递归排列后面的元素。

有重复元素时全排列如何去重？

通常先排序，然后在同层选择时跳过与前一个相同且前一个未使用的元素，避免生成重复分支。去重必须发生在同一递归层，而不是最后用 Set 粗暴兜底。

“回溯生成全排列”追问实现细节时，应该展开哪条链路？

用回溯生成全排列，维护当前路径 path 和 used 标记。每一层选择一个未使用元素加入路径，递归到长度为 n 时收集一个排列，然后撤销选择继续尝试。面试官继续追问时，应该沿着这条机制展开：模板是 choose -> recurse -> unchoose。若数组有重复元素，先排序，并在同层跳过 nums[i] === nums[i-1] 且前一个未使用的分支，避免重复排列。

“回溯生成全排列”怎么验证结论没有答偏？

优先给出能观察或推导的证据：用 [1,2,3] 和 [1,1,2] 验证数量、去重和回溯撤销是否正确。同时补充失败边界：要说明空数组、重复元素、输出顺序、递归深度和结果规模爆炸。不要把全排列讲成随机排列或采样题，主线始终是路径选择、递归和撤销选择。

“如何用回溯法生成全排列”继续追问时最该补哪条边界？

应该围绕“回溯生成全排列”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。