难度中等1308
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
解题思路：回溯
这道题其实和 46. 全排列 一样的，只不过是不一样的是 nums 中存在着重复元素，那么我们肯定是要去重的，和 40. 组合总和 II 这道题是一样的，通过一个 used 数组来进行树层上的去重，但是前提是这个 nums 得先排序，因为我们这个判断条件是基于 nums[i] == nums[i - 1] ，所以要先排序！
为了可读性，我这里先用两个不同的 used 数组来表示树枝和树层的去重：
class Solution {
public:
void backtracking(vector<int>& nums, vector<bool>& usedlayer, vector<bool>& usedbranch)
{
if(nums.size() == v.size())
{
vv.push_back(v);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
// 判断树层的同值元素是否使用过
if(i > 0 && nums[i] == nums[i - 1] && usedlayer[i - 1] == false)
continue;
// 判断树枝的当前元素是否被使用过
if(usedbranch[i] == true)
continue;
v.push_back(nums[i]); // 处理
usedbranch[i] = true;
usedlayer[i] = true;
backtracking(nums, usedlayer, usedbranch); // 递归
usedbranch[i] = false; // 回溯
usedlayer[i] = false;
v.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> usedlayer(nums.size(), false);
vector<bool> usedbranch(nums.size(), false);
sort(nums.begin(), nums.end()); // 先排序才能去掉树层重复
backtracking(nums, usedlayer, usedbranch);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
}; 其实我们可以只用一个 used 数组就能实现，因为我们判断树层是用 false，而树枝是用 true，在递归和回溯的时候其实就改变了 used 的状态，两者互不干扰：
class Solution {
public:
void backtracking(vector<int>& nums, vector<bool>& used)
{
if(nums.size() == v.size())
{
vv.push_back(v);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
// 判断树层的同值元素是否使用过
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
continue;
// 判断树枝的当前元素是否被使用过
if(used[i] == true)
continue;
v.push_back(nums[i]); // 处理
used[i] = true;
backtracking(nums, used); // 递归
used[i] = false; // 回溯
v.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 先排序才能去掉树层重复
backtracking(nums, used);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
};拓展：
大家发现，去重最为关键的代码为：
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
} 如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
continue;
} 这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
这么说是不是有点抽象？
来来来，我就用输入: [1,1,1] 来举一个例子。
树层上去重(used[i - 1] == false)，的树形结构如下：
树枝上去重（used[i - 1] == true）的树型结构如下：
大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。