题解 | #有重复项数字的全排列#

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //先使数组保持一个递增方向  利于字典序升序排序
        Arrays.sort(num);
        
        dfs(num,list,new boolean[num.length]);
        return res;
    }
    //思路还是使用dfs进行全排列 ，进行适当剪枝
    public void dfs(int num[] ,ArrayList<Integer> list ,boolean []used){
        if(list.size() == num.length) {
            res.add(new ArrayList<>(list));
            return ;
        }

        for(int i = 0 ; i < num.length ; i++){
            //当前数字正在被使用
            if(used[i]) continue; 
            //如果当前这个数和上一个数相等 没有保持一个递增方向 并且上一个数已经没有被使用了
            //则这次情况和上次的相同 进行剪枝
            if(i > 0 && num[i - 1] == num[i] && !used[i-1]) continue;

            //否则 进行dfs
            used[i] = true;
            list.add(num[i]);
            dfs(num,list,used);
            list.remove(list.size()-1);
            used[i] = false;
        }
    }
}