去重判断 是!vis[i - 1] 而非 vis[i - 1] 详解

为什么去重判断是 !vis[i - 1] 而非 vis[i - 1]

在处理全排列时，尤其是含有重复字符的场景（如 AAB），为了避免重复的排列结果，需要在递归过程中跳过某些重复的选择。判断条件 chars[i] == chars[i - 1] && !vis[i - 1] 的设计是为了确保当前重复字符只有在前一个相同字符已经被选择的情况下才可以继续选择。具体原因详解如下：

去重的核心逻辑

1. 排序是前提

将输入字符串或数组排序（例如，AAB 排序为 ['A', 'A', 'B']），确保相同字符相邻。这样可以方便地判断当前字符是否与前一个字符重复。

2. chars[i] == chars[i - 1]

• 这一部分检查当前字符是否与前一个字符相同。
• 如果相同，说明是重复字符，需要进一步判断是否跳过。

3. !vis[i - 1] 的意义

• 如果 !vis[i - 1] 为 true（即前一个字符尚未被访问），说明当前递归分支还未处理过重复字符的排列，此时跳过当前字符以避免重复。
• 如果 vis[i - 1] 为 true，说明前一个字符已经被访问并处理过，当前字符可以作为后续递归的一部分。

核心思想

!vis[i - 1] 的目的是确保：

• 每一层递归中，同一层的重复字符只选择一次。
• 后续递归中，重复字符仍可以被合法选择。

为什么不是 vis[i - 1]？

如果去重条件写为 chars[i] == chars[i - 1] && vis[i - 1]，问题在于：

• 逻辑错误：当 vis[i - 1] == true 时，当前字符实际上已经被递归分支合法处理过，但条件却要求跳过，这会导致遗漏某些合法的排列。
• 例如，对于输入字符串 AAB，某些递归分支可能会被错误跳过，结果不完整。

以具体递归为例

输入字符串："AAB"

排序后：['A', 'A', 'B']

递归流程对比

正确逻辑：chars[i] == chars[i - 1] && !vis[i - 1]

最终结果： [AAB, ABA, BAA]

错误逻辑：chars[i] == chars[i - 1] && vis[i - 1]

最终结果： [AB]
由于错误的条件跳过了合法分支，排列结果不完整。

!vis[i - 1] 的关键意义

1. 递归层次控制

   • 在同一层递归中，重复字符只能由第一个未被访问的字符负责分支生成，避免重复排列。
   • 通过 !vis[i - 1] 跳过其他重复字符，减少冗余计算。

2. 递归分支合法性

   • 在递归的下一层（或更深层次），前一个相同字符已经参与排列，当前字符可以作为下一层递归的一部分，无需跳过。

3. 去重的前提是排序

   • 排序确保重复字符相邻，使得 chars[i] == chars[i - 1] 成立时，能够明确其去重逻辑是否需要跳过。

总结：为什么是 !vis[i - 1]

1. 避免同层重复选择：

   • 如果前一个相同字符未被访问（!vis[i - 1]），说明当前字符在同一层中属于重复选择，跳过当前字符。

2. 允许后续分支合法访问：

   • 如果前一个相同字符已经被访问（vis[i - 1]），说明当前字符是合法选择的一部分，可以继续递归。

3. 排序+标记数组确保唯一性：

   • 排序使相同字符相邻，标记数组 vis[] 确保字符是否已访问，从而有效去重。

所以，!vis[i - 1] 的判断方式是正确的去重逻辑核心，它保证了排列结果的唯一性和完整性。