public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> res = new ArrayList<>();
        if (num.length==0) return res;
        Arrays.sort(num); //sort so that duplicate numbers come together
        boolean[] visited = new boolean[num.length];
        List<Integer> ans = new ArrayList<>();
        helper(num,visited,ans,res);
        return res;

    }

    public void helper(int[] num, boolean[] visited, List<Integer> ans, List<List<Integer>> res){
        if (ans.size()==num.length){
            res.add(new ArrayList(ans));
            return;
        }

        for(int i=0;i<num.length;i++){
            if (!visited[i]){
                visited[i]=true;
                ans.add(num[i]);
                helper(num,visited,ans,res);
                visited[i]=false;
                ans.remove(ans.size()-1);
                //back track. take care of the dups.
                while(i<num.length&&num[i]==num[i+1]) i++;//note that i will be incremented in the for loop, so it refers to the non duplicate element;
            }
        }
    }
}