03、全排列II

当数组里有两个 1，交换它们的位置会得到两个搜索过程，却不一定得到两个不同答案。全排列 II 的难点不是生成排列，而是在生成过程中避免重复分支。

问题与目标

LeetCode 47：全排列 II允许输入包含重复数字，要求返回所有不同的排列。

输入：[1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]

与普通全排列不同，本题既要保证每个下标只使用一次，也要保证相同数值不会在同一位置重复开头。

先分清两种“重复”

第一种是重复使用同一个元素下标。used[i] 为真时，说明这个下标已经出现在当前路径中，不能再选。

第二种是重复生成相同数值的排列。先排序让相同元素相邻，再使用下面的判断跳过同层重复候选：

i > 0 && nums[i] == nums[i - 1] && !used[i - 1]

如果前一个相同元素没有在当前路径中使用，就不让后一个相同元素先出场；反过来，前一个相同元素已经在路径里时，后一个可以进入下一层。例如 [1,1,2] 的两个 1 都需要保留，不能把相同数值全部删除。

用有编号的两个 1 推导

仅为分析，把两个相同数值记成 1a、1b，但最终答案仍然只存数字 1。

1. 在空路径处，先选 1a；下一层允许选 1b，于是可以得到 [1,1,2]。
2. 回到空路径，如果再让 1b 开头，会重复得到与 1a 开头相同的数值排列。因此跳过这个同层入口。
3. 空路径选择 2 后，同样让 1a 先于 1b 使用，得到 [2,1,1]。

排序不是为了让答案整体有序，而是让“前一个相同候选”可以被直接比较。

C++17 实现

#include <algorithm>
#include <vector>

class Solution {
 public:
  std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> answers;
    std::vector<int> path;
    std::vector<bool> used(nums.size(), false);
    search(nums, used, path, answers);
    return answers;
  }

 private:
  void search(const std::vector<int>& nums, std::vector<bool>& used,
              std::vector<int>& path, std::vector<std::vector<int>>& answers) {
    if (path.size() == nums.size()) {
      answers.push_back(path);
      return;
    }
    for (std::size_t i = 0; i < nums.size(); ++i) {
      if (used[i]) continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      path.push_back(nums[i]);
      search(nums, used, path, answers);
      path.pop_back();
      used[i] = false;
    }
  }
};

复杂度与边界

排序需要 O(n log n)。最坏情况下所有元素不同，搜索及复制答案的时间为 O(n·n!)；重复值会减少实际分支。除结果外，路径、标记和递归栈共 O(n) 空间，K 个答案另占 O(Kn)。

代码会原地排序输入。如果调用者需要保留原顺序，应先复制输入。对题目范围外的空数组，本实现返回一个空排列 [[]]，符合组合枚举中“空序列有一种排列”的约定。

常见误区

• 只判断 used[i]：能防止重复使用下标，但不能去掉相同数值产生的重复答案。
• 只比较相邻数值，不判断 used[i - 1]：会把不同层中本应使用的第二个 1 也剪掉。
• 把整条路径中存在某个数值视为不能再选：混淆了元素下标和元素值。
• 直接对所有排列做集合去重：可以用来对照验证，但会先生成大量无效分支，不是本文主解。