LeetCode - Permutations II

PermutationsII.java

// Original solution -- recursive
public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.length == 0) return ret;
        Arrays.sort(nums);
        boolean[] flags = new boolean[nums.length];
        helper(ret, flags, nums, new ArrayList<Integer>(), 0);
        return ret;
    }
    
    public void helper(ArrayList<ArrayList<Integer>> ret, boolean[] flags, int[] nums, ArrayList<Integer> lst, int p){
        if(lst.size() == nums.length){
            ret.add(new ArrayList<Integer>(lst));
            return;
        }
        for(int i=0; i < nums.length; i++){
            if(!flags[i] && (i==0 || i>0 && nums[i] != nums[i-1] || i>0 && nums[i] ==nums[i-1] && flags[i-1])){
                flags[i] = true;
                lst.add(nums[i]);
                helper(ret, flags, nums, lst, p+1);
                lst.remove(lst.size()-1);
                flags[i] = false;
            }
        }
    }
    
// better solution -- recursive
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        if(num==null || num.length==0) return null;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        helper(num, new boolean[num.length], new ArrayList<Integer>(), ret);
        return ret;
    }
    
    private void helper(int[] num, boolean[] used, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> ret){
        if(temp.size() == num.length){
            ret.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i=0; i<num.length; i++){
            if(i>0 && !used[i-1] && num[i]==num[i-1]) continue;
            if(!used[i]){
                used[i] = true;
                temp.add(num[i]);
                helper(num, used, temp, ret);
                temp.remove(temp.size()-1);
                used[i] = false;
            }
        }
    }

// iterative  --- use hashset
public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) return ret;
        Arrays.sort(nums);
        ret.add(new ArrayList<Integer>());
        for(int i=0; i<nums.length; i++){
            Set<List<Integer>> newRet = new HashSet<List<Integer>>();
            for(int j=0; j<ret.size(); j++){
                for(int k=0; k<=ret.get(j).size(); k++){
                    List<Integer> lst = new ArrayList<Integer>(ret.get(j));
                    lst.add(k, nums[i]);
                    newRet.add(lst);
                }
            }
            ret = new ArrayList<List<Integer>>(newRet);
        }
        return ret;
    }
// iterative ---another way
public List<List<Integer>> permuteUnique(int[] num) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < num.length; i++) {
            Set<String> cache = new HashSet<>();
            while (res.peekFirst().size() == i) {
                List<Integer> l = res.removeFirst();
                for (int j = 0; j <= l.size(); j++) {
                    List<Integer> newL = new ArrayList<>(l.subList(0,j));
                    newL.add(num[i]);
                    newL.addAll(l.subList(j,l.size()));
                    if (cache.add(newL.toString())) res.add(newL);
                }
            }
        }
        return res;
    }