1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

ArrayList<ArrayList<Integer>> ans  = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ArrayList<Integer> track = new ArrayList<>();
        boolean[] used = new boolean[num.length];
        Arrays.sort(num);
        backtrack(num, track, used);
        return ans;
    }

    private void backtrack(int[] num,ArrayList<Integer> track,boolean[] used){
        if(track.size()==num.length){
            ans.add(new ArrayList<>(track));
            return;
        }

        for(int i=0;i<num.length;i++){
            if(used[i]){
                continue;
            }

            if(i>0&&num[i]==num[i-1]&&!used[i-1]){
                continue;
            }

            track.add(num[i]);
            used[i]=true;
            backtrack(num, track, used);
            track.remove(track.size()-1);
            used[i]=false;
        }
    }