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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    int[] used = null;
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        ArrayList<Integer> path = new ArrayList<>();
        used = new int[num.length];
        Arrays.sort(num);
        dfs(num,path,0);
        return list;
    }
    public void dfs(int[] num,ArrayList<Integer> path,int index){
        if(index == num.length){
            list.add(new ArrayList<>(path));
        }
        for(int i=0;i<num.length;i++){
            //剪枝，如果前一个元素与当前元素相同，且前一个元素未被使用
            if(i>0&&num[i]==num[i-1]&&used[i-1]==0) continue;
            if(used[i]==1) continue;
            
            used[i] = 1;
            path.add(num[i]);
            dfs(num,path,index+1);
            path.remove(path.size()-1);
            used[i] = 0;
        }
    }
}