P3805. 文档碎片拼接

解题思路

本题属于排列回溯问题的板子题，和 经典题型. 全排列 II 几乎完全一致。

核心要点：去重

唯一需要注意的是去重。参考代码用了两层保险：

1. 排序 + 同层跳过：先把 n 个纸片字符串排序，让内容相同的纸片相邻；回溯每层枚举时，若 words[i] == words[i-1] 且 used[i-1] 为假（表示同一层里前一个相同纸片刚被撤销选择），直接跳过——再选当前这个只会产生完全相同的排列。这正是题目备注「仅相同碎片间的位置变化不影响组合」在代码里的落点。 2. `ans_set` 哈希表兜底：拼出完整文档字符串后再经 ans_set 判重，确认没出现过才收入答案列表。

（另一种常见的同层去重写法是每层维护一个局部 set 记录本层已尝试过的元素，效果等价；参考代码采用的是上面「排序 + 相邻跳过」的写法。）

思路展开

回溯函数用 used 数组标记每个纸片是否已进入当前路径，path 保存当前已选的纸片序列；每层横向遍历所有纸片，跳过已用过的与同层重复的。当 path 长度等于 n 时，把纸片按路径顺序拼成完整文档字符串，经 ans_set 判重后收入答案列表，与同层去重构成双保险。最后对答案列表整体排序后逐行输出。

复杂度分析

• 设纸片数为 n，所有纸片内容总长为 L。同层去重后生成的不同排列个数上界为 n!（存在重复纸片时会显著减少），每生成一个完整排列需要 O(L) 的拼接与集合判重（字符串哈希代价与长度成正比），故总时间复杂度上界为 O(n! × L)。
• 预处理排序为 O(n log n) 次字符串比较，答案排序代价与结果总量相关，均不构成瓶颈。
• 空间复杂度：递归栈、used、path 为 O(n)；ans 与 ans_set 存放所有不同结果，占 O(结果总数 × L)。

坑点提醒

• 回溯前必须先对 words 排序，否则「跳过相邻相同元素」的同层去重不成立。
• 参考代码在输出前对答案列表整体排序（代码注释注明「必须对答案列表进行排序」），漏掉这步会导致输出顺序不对。