递归-带重复数字的全排列

带重复数字的处理比普通的全排列多在不重复处理相同数字

比如选取第一个数字时，我们应选了重复数字的其中一项，那么重复数字的其他项我们就不用再在第一个数字时选择

于是我们需要知道这个数字是否是重复数字，而且在每一次选择时知道我们前一个刚处理了当前这个数字的重复项

这里有一个方法就是将数字进行排序，此时，所有相同的数字就会排在一起

当我们在循环遍历某一位选择哪个数字时，我们可以判断下前面的数字是否与当前的数字相同，且前面的数字是否已经使用过，如果没使用过，我们则跳过这个分支

如果有使用过，我们可以继续使用

这种是通过使用的有序性来保证我们不出现重复选择相同数字导致的重复的排列结果

class Solution {
    // 定义结果变量
    List<List<Integer>> res;
    // 定义结果项变量
    List<Integer> resItem;
    // 定义状态数组
    boolean[] status;
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 排序
        Arrays.sort(nums);
        int size = nums.length;
        // 初始化变量
        res =  new ArrayList<>();
        resItem = new ArrayList<>();
        status = new boolean[size];
        // 递归遍历 所有可能
        dfsList(0, nums);
        // 返回
        return res;
    }

    private void dfsList(int u, int[] nums) {
        // 递归结束条件
        if(u==nums.length){
            res.add(new ArrayList<Integer>(resItem));
            return;
        }
        // 循环遍历
        for(int i=0;i<nums.length;i++){
            boolean curStatus = status[i];
            // 如果已经访问过的跳过
            if(curStatus){
                continue;
            }
            int curItem = nums[i];
            // 如果前面的当前元素和前面元素相同，且前面元素未访问过，tiaoguo
            if(i>0 && nums[i-1]==curItem && !status[i-1]){
                continue;
            }
            // 更新结果项
            resItem.add(curItem);
            // 更新状态数组
            status[i] = true;
            // 递归下一层
            dfsList(u+1, nums);
            //回溯 结果项
            status[i] = false;
            // 回溯 状态数组
            resItem.remove(resItem.size()-1);
        }

    }
}