47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

分析：在全排列的基础上加上了限制条件不重复。可以直接用全排列的代码进行剪纸操作。如图

我们发现在每层计算中，只需要计算第一次出现的数字，再出现重复的数字无需运算。

所以我们可以在每层中使用Set进行去重。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        backstack(nums,0,nums.length,res);
        return res;
    }

    private void backstack(int[] nums,int begin,int end, List<List<Integer>> res){
        if(begin==end){
            List<Integer> tem = new ArrayList<Integer>();
            for (int n = 0; n < nums.length; n++) {
                tem.add(nums[n]);
            }
            res.add(tem);
            return;
        }
        
        Set<Integer> set=new HashSet<>();
        for (int i = begin; i <end; i++) {//begin-end 之间的全排列
           if(set.contains(nums[i]))//去重
                continue;
            set.add(nums[i]);
            swap(nums,i,begin);
            backstack(nums,begin+1,end,res);
            swap(nums,i,begin);

        }
    }

    private  void swap(int[] nums, int x, int y) {
        int a = nums[x];
        nums[x] = nums[y];
        nums[y] = a;
    }
}