P3800. 第N个排列

解题思路

这道题本质上是一道排列类型的回溯问题。具体过程和 全排列 几乎完全一致。

剪枝操作

注意本题可以进行剪枝操作，即无需计算所有排列，只需要计算前 k 个排列即可。

补充说明

但不做剪枝也可以通过全部用例。

思路展开 代码是一次标准的排列型回溯，只是把「收集所有排列」换成了「数到第 k 个就停」。usedList 记录 1 到 n 中哪些数字已进入当前路径，path 保存当前已选的数字序列。递归中横向遍历时 i 从 1 到 n 递增枚举，每层总是优先尝试更小的数字，因此完整排列被生成的先后顺序恰好就是题目要求的升序（字典序），这是本解法不需要额外排序的关键。每生成一个长度为 n 的完整排列，计数器 cnt 加一；当 cnt 恰好等于 k 时，把 path 拼接成字符串存入 ans。每次回滚之后还有一个剪枝判断：一旦 cnt 已达到 k，后续回溯全部提前返回，不再生成第 k 个之后的排列。

复杂度分析

• 设 n 为数字个数，k 为目标序号。由于生成顺序即升序，找到第 k 个排列后立即剪枝返回，实际完整生成的排列恰好是前 k 个；生成一个排列沿途的回溯节点数与拼接代价为 O(n)，故时间复杂度为 O(k × n)，最坏情况（k = n!）退化为 O(n! × n)。
• 空间复杂度为 O(n)：递归深度最深为 n，path 与 usedList 均为 O(n)。

边界与注意事项

• 升序生成依赖「每层从 1 到 n 递增枚举」这一写法，改动枚举顺序会破坏字典序性质。
• n = 1 时只有一个排列，回溯第一层即命中。
• 若传入的 k 超过全部排列数 n!，回溯自然结束而 cnt 达不到 k，ans 保持初始空串，代码输出空行，不会报错。
• 剪枝判断写在回滚之后，保证命中答案的那条路径先完成状态回滚再逐层退出，path 与 usedList 不会残留脏状态。