给定一个可包含重复数字的序列
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]]与46. 全排列类似，区别在于：数组中包含重复元素。
对于重复的元素，可以像40. 组合总和 II的题解那样，先把数组排序，跳过值相等的两个元素。
第二类：对某种数结构和算法的使用
使用的算法：在给定的元素集合中，找到所有满足条件的排列，使用“回溯算法“
数据结构：回溯算法需要构建空间状态树，使用树结构
“回溯算法”要确定以下条件，然后构建出解集的空间状态树。
（1）选择列表
因为排列包含所有元素，所以选择列表是整个数组。
（2）路径
记录已经选择的元素值，在一个排列中，每个元素只能使用一次，所以要记录每个下标的元素是否被使用。
（3）结束条件
达到什么条件时结束结束当前节点的遍历？
路径中元素个数等于数组中元素个数，表示已经没有元素未被选中，把路径添加到结果集中。
（4）选择
什么条件下才把当前元素添加进路径中？
- 当前元素没有被选择进当前序列
- 如果和前一个元素值相等，那么只有当前一个元素被选择进序列了，当前元素才会被选择
为什么要求前一个相同值的元素？
“空间状态树”如下图所示，图中
从40. 组合总和 II题解中可知，如果两个元素$nums[i-1]、nums[i]$值相等且不在同一层递归中，那么第二个元素可添加进路径中，在40. 组合总和 II的题解中，每层递归都是从$i=idx$开始遍历，所以可以根据
在本题的状态树中，每一层递归都会从数组下标0开始遍历，没有额外参数$idx$，当遍历到下标$i$时，无法知道$nums[i-1]、nums[i]$两者是否在同一层递归中。
但是从图中可以发现另外的关系，来判断$nums[i]$是否可以添加进路径中：
用$D_{i}$表示遍历到元素$nums[i]$，$A_{i}$表示同层递归中的元素$nums[i]$在路径中，$B_{i}$表示不同层递归中的元素$nums[i]$在路径中，$C_{i}$表示可以把元素$nums[i]$添加进路径中。
从状态图中可知，在某一层递归中，从下标0开始遍历到$i$时，同层递归中的元素$nums[i-1]$会从路径中移除，所以必然有：$D_{i} \rightarrow \overline{A_{i}}$，这时有两种情况：
1、如果不同层递归中的元素$nums[i-1]$在路径中，那么可以把当前层递归中的元素$nums[i]$添加进路径，所以有：$B_{i-1} \rightarrow C_{i}$
2、如果不同层递归中的元素$nums[i-1]$不在路径中，说明在遍历到当前层递归中的元素$nums[i-1]$时，所有以$nums[i-1]$开头的排列都已经保存进结果集中，此时如果再把元素$nums[i]$添加进路径，会导致重复排序，不满足题目需要，所以有：$\overline{B_{i-1}} \rightarrow \overline{C_{i}}$
根据上面的两个关系，只需要判断元素$nums[i-1]$不在路径中，就可以跳过元素$nums[i]$。
class Solution {
public static void main(String[] args) {
int[] nums = new int[]{1, 1, 2};
System.out.println("=======" + new Solution().permuteUnique(nums));
}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>(nums.length);
// index[i] == true，表示下标 i 处的元素已经被添加进路径
boolean[] index = new boolean[nums.length];
Arrays.fill(index, false);
backtrack(res, path, index, nums);
return res;
}
public void backtrack(List<List<Integer>> res, List<Integer> path, boolean[] index, int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (index[i]) {
continue;
}
// 如果和前一个元素值相等，且前一个元素没有被选择，就跳过当前元素
if (i > 0 && nums[i] == nums[i - 1] && !index[i - 1]) {
continue;
}
path.add(nums[i]);
index[i] = true;
backtrack(res, path, index, nums);
path.remove(path.size() - 1);
index[i] = false;
}
}
}排列与组合不同，每次递归中要从下标0开始遍历数组中的每个元素，对于重复元素，要利用“空间状态树”的特点，根据前一个元素是否在路径中，确定当前元素是否要添加进路径中。