Permutations II

 Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Have you been asked this question in an interview?

public class Solution {

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();

        if(num==null || num.length==0) {

            return ret;

        }

        Arrays.sort(num);

        ret.add(new ArrayList<Integer>());

        for(int n : num) {

            ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();

            HashSet<String> set = new HashSet<String>();

            for(ArrayList<Integer> lst : ret) {

                for(int i=0;i<=lst.size();i++) {

                    ArrayList<Integer> newLst = new ArrayList<Integer>(lst);

                    newLst.add(i, n);

                    StringBuilder sb = new StringBuilder();

                    for(int j : newLst) {

                        sb.append(j).append("_");

                    }

                    if(!set.contains(sb.toString())) {

                        tmp.add(newLst);

                        set.add(sb.toString());

                    }

                }

            }

            ret = tmp;

        }

        return ret;

    }

}

=================

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        permutating(ans, nums, 0);
        return ans;
    }
 
    private void permutating(List<List<Integer>> ans, int[] nums, int start) {
        if (start == nums.length - 1) {
            List<Integer> li = new ArrayList<>();
            for (int n : nums) {
                li.add(n);
            }
            ans.add(li);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[start] == nums[i]) {
                continue;
            }
            swap(nums, start, i);
            permutating(ans, Arrays.copyOf(nums, nums.length), start+1);
        }
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

================


public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        permutating(ans, nums, 0);
        return ans;
    }
 
    private void permutating(List<List<Integer>> ans, int[] nums, int start) {
        if (start == nums.length - 1) {
            List<Integer> li = new ArrayList<>();
            for (int n : nums) {
                li.add(n);
            }
            ans.add(li);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[start] == nums[i]) {
                continue;
            }
            if (i != start)
                swap(nums, start, i);
            permutating(ans, Arrays.copyOf(nums, nums.length), start + 1);
        }
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

=======

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean visit[] = new boolean[nums.length];
        helper(nums, visit, new ArrayList<Integer>(), res);
        return res;
    }
   
    private void helper(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == nums.length) {
            List<Integer> newList = new ArrayList<Integer>(list);
            res.add(newList);
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) {
                    continue;
                }
                if (i != 0 && nums[i] == nums[i - 1] && visited[i - 1]) {
                    continue;
                }
                list.add(nums[i]);
                visited[i] = true;
                helper(nums, visited, list, res);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }
}