排列问题的输入如果存在重复，比子集/组合问题稍微复杂一点，我们看看力扣第 47 题「 全排列 II 」：
给你输入一个可包含重复数字的序列 nums，请你写一个算法，返回所有可能的全排列，函数签名如下：
List<List<Integer>> permuteUnique(int[] nums)
比如输入 nums = [1,2,2]，函数返回：
[ [1,2,2],[2,1,2],[2,2,1] ]
先看解法代码：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
track.add(nums[i]);
used[i] = true;
backtrack(nums);
track.removeLast();
used[i] = false;
}
}
}你对比一下之前的标准全排列解法代码，这段解法代码只有两处不同：
1、对 nums 进行了排序。
2、添加了一句额外的剪枝逻辑。
类比输入包含重复元素的子集/组合问题，你大概应该理解这么做是为了防止出现重复结果。
但是注意排列问题的剪枝逻辑，和子集/组合问题的剪枝逻辑略有不同：新增了 !used[i - 1] 的逻辑判断。
这个地方理解起来就需要一些技巧性了，且听我慢慢到来。为了方便研究，依然把相同的元素用上标 ' 以示区别。
假设输入为 nums = [1,2,2']，标准的全排列算法会得出如下答案：
[
[1,2,2'],[1,2',2],
[2,1,2'],[2,2',1],
[2',1,2],[2',2,1]
]
显然，这个结果存在重复，比如 [1,2,2'] 和 [1,2',2] 应该只被算作同一个排列，但被算作了两个不同的排列。
所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？
答案是，保证相同元素在排列中的相对位置保持不变。
比如说 nums = [1,2,2'] 这个例子，我保持排列中 2 一直在 2' 前面。
这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：
[ [1,2,2'],[2,1,2'],[2,2',1] ]
这也就是正确答案。
进一步，如果 nums = [1,2,2',2'']，我只要保证重复元素 2 的相对位置固定，比如说 2 -> 2' -> 2''，也可以得到无重复的全排列结果。
相当于固定住了 2-2‘-2“，把他当为 X，因为只有一种固定顺序
仔细思考，应该很容易明白其中的原理：
标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
那么反映到代码上，你注意看这个剪枝逻辑：
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
// 如果前面的相邻相等元素没有用过，则跳过
continue;
}
// 选择 nums[i]当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
这里拓展一下，如果你把上述剪枝逻辑中的 !used[i - 1] 改成 used[i - 1]，其实也可以通过所有测试用例，但效率会有所下降，这是为什么呢？
之所以这样修改不会产生错误，是因为这种写法相当于维护了 2'' -> 2' -> 2 的相对顺序，最终也可以实现去重的效果。
但为什么这样写效率会下降呢？因为这个写法剪掉的树枝不够多。
比如输入 nums = [2,2',2'']，产生的回溯树如下：
如果用绿色树枝代表 backtrack 函数遍历过的路径，红色树枝代表剪枝逻辑的触发，那么 !used[i - 1] 这种剪枝逻辑得到的回溯树长这样
而 used[i - 1] 这种剪枝逻辑得到的回溯树如下：
可以看到，!used[i - 1] 这种剪枝逻辑剪得干净利落，而 used[i - 1] 这种剪枝逻辑虽然也能得到无重结果，但它剪掉的树枝较少，存在的无效计算较多，所以效率会差一些。
当然，关于排列去重，也有读者提出别的剪枝思路：
void backtrack(int[] nums, LinkedList<Integer> track) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
// 记录之前树枝上元素的值
// 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
int prevNum = -666;
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) {
continue;
}
if (nums[i] == prevNum) {
continue;
}
track.add(nums[i]);
used[i] = true;
// 记录这条树枝上的值
prevNum = nums[i];
backtrack(nums, track);
track.removeLast();
used[i] = false;
}
}这个思路也是对的，设想一个节点出现了相同的树枝：
如果不作处理，这些相同树枝下面的子树也会长得一模一样，所以会出现重复的排列。
因为排序之后所有相等的元素都挨在一起，所以只要用 prevNum 记录前一条树枝的值，就可以避免遍历值相同的树枝，从而避免产生相同的子树，最终避免出现重复的排列。
好了，这样包含重复输入的排列问题也解决了。