给定一个可包含重复数字的序列 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. 全排列 的解题笔记！
但是与 46. 全排列 不同的是，这道题给定的数字序列，是可包含重复元素的，也就是说决策树中可能会出现相同的子树，也就是有重复的结果出现，如下图所示：
所以我们必须做点措施，防止重复决策子树出现！（也可以用哈希表去重，但是比较占空间，这里不考虑）
方法其实很简单，我们仔细一想，会出现重复的情况，其实就是因为有重复的元素，那么我们只要让重复的元素只遍历一次决策子树，而其它重复的元素不处理即可，所以我们考虑先将原数组进行排序，这样子使得重复的元素是相邻的，然后我们只需要用已有的 used 数组多加一层判断即可！具体判断的细节如下所示：
- 对于不同层的元素的剪枝处理：
- 如果上一层走过了该节点，那么就不需要再走了，也就是如果
used[i] == true则直接跳过即可！
- 如果上一层走过了该节点，那么就不需要再走了，也就是如果
- 对于同层的元素的剪枝处理：
- 如果相邻元素重复的话，那么当前元素其决策子树是和前面重复的，必须得进行剪枝操作，也就是此时
i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false成立的话则直接跳过即可！
- 如果相邻元素重复的话，那么当前元素其决策子树是和前面重复的，必须得进行剪枝操作，也就是此时
上面的判断，相比起 46. 全排列 这道题来说只不过多了一个对同层元素的剪枝处理，如下图所示：
其它细节都是一样的，这里不再赘述！
class Solution {
private:
vector<vector<int>> ret; // 存放结果集
vector<int> path; // 存放当前路径中的元素
bool used[9]; // 保存元素是否已经走过，true表示走过
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
// 首先对原数组进行排序，使得重复的元素是相邻的
sort(nums.begin(), nums.end());
// 然后交给递归函数去求解结果即可
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
// 递归函数出口
if(path.size() == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
// 如果上一层走过了该节点，那么就不需要再走了（注意这是对不同层的剪枝处理）
// 进行剪枝操作，如果相邻元素重复的话，其排列结果是和前面重复的（注意这是对同层的剪枝处理）
if(used[i] == true || (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false))
continue;
// 处理当前元素
path.push_back(nums[i]);
used[i] = true;
// 递归处理该节点以下的路径
dfs(nums);
// 回溯处理
used[i] = false;
path.pop_back();
}
}
};