含重复字符字符串全排列实现中HashMap用法与回溯逻辑咨询

两行map.put代码的作用 #

这是回溯算法中标准的「状态修改-状态还原」操作，对应排列生成中「用掉当前字符」和「归还当前字符」的逻辑：

• map.put(c, count - 1)：确定当前排列位置选字符c，所以将它的剩余可用次数减1，再进入下一层递归，生成当前前缀之后的剩余排列部分。
• map.put(c, count)：下一层递归执行完毕，所有以prefix + c为前缀的排列已经全部生成完成，将c的剩余可用次数还原为初始值，避免影响当前循环中其他字符分支的执行。

为什么HashMap能解决重复排列问题 #

普通无重复字符的全排列，通常是遍历原字符串下标，用标记数组记录下标是否被使用。但如果输入有重复字符，比如aab中的两个a是完全等价的，选第一个a和第二个a生成的排列完全一致，就会出现大量重复结果。
这个实现中用HashMap存储去重后的字符种类，以及每种字符的剩余可用次数，循环遍历的是map.keySet()也就是不同的字符，而非原字符串的下标：同一层递归中，同一个字符只会被选择一次，不会因为原字符串中有多个相同字符就走重复分支，从根源上避免了重复排列的生成。
你给出的对比示例也验证了这一点：不基于频率统计的实现，会把重复字符当作不同个体处理，甚至会生成超出原字符串字符出现次数的非法排列（比如输入是ab时输出aa），而HashMap实现严格限制了每种字符的使用次数，既不会生成非法排列，也不会出现重复结果。

回溯逻辑的执行逻辑梳理 #

我们以输入aab（a剩余2次、b剩余1次）为例，整个排列生成过程就是逐层确定当前位置的字符：

1. 第一层（前缀为空，剩余3个字符待填充）：可选字符为a、b
   • 选a：a剩余次数改为1，前缀变为a，进入第二层递归
     1. 第二层（剩余2个字符待填充）：可选字符为a（剩余1）、b（剩余1）
        • 选a：a剩余次数改为0，前缀变为aa，进入第三层递归
          1. 第三层（剩余1个字符待填充）：a剩余为0无法选择，只能选b，前缀变为aab，剩余字符数为0，加入结果集；回滚b的次数为1，第三层递归结束
          2. 回滚a的次数为1，回到第二层
        • 选b：b剩余次数改为0，前缀变为ab，进入第三层递归
          1. 第三层（剩余1个字符待填充）：b剩余为0无法选择，只能选a，前缀变为aba，加入结果集；回滚a的次数为1，第三层递归结束
          2. 回滚b的次数为1，第二层递归结束
     2. 回滚a的次数为2，回到第一层
   • 选b：b剩余次数改为0，前缀变为b，进入第二层递归
     1. 第二层（剩余2个字符待填充）：b剩余为0无法选择，只能选a，a剩余次数改为1，前缀变为ba，进入第三层递归
        1. 第三层（剩余1个字符待填充）：只能选a，前缀变为baa，加入结果集；回滚a的次数为1，第三层递归结束
     2. 回滚b的次数为1，第一层递归结束
        整个过程没有冗余的重复分支，最终生成的结果就是无重复的[aab, aba, baa]。

内容的提问来源于stack exchange，提问作者Pingpong