Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.

Have you met this question in a real interview? 

Yes

Example

For numbers [1,2,2] the unique permutations are:

[

    [1,2,2],

    [2,1,2],

    [2,2,1]

]

Challenge

Do it without recursion.

class Solution {

    /**

     * @param nums: A list of integers.

     * @return: A list of unique permutations.

     */

    public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {

        // write your code here

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

        if(nums == null) return res;

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

        

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

            int num = nums.get(i);

            HashSet<ArrayList<Integer>> set = new  HashSet<ArrayList<Integer>>();

            for(ArrayList<Integer> list : res){

                for(int j = 0; j < list.size() + 1; j++){

                    list.add(j, num);

                    set.add(new ArrayList<Integer>(list));

                    list.remove(j);

                }

            }

            res = new ArrayList<ArrayList<Integer>>(set);

        }

        return res;

        

    }

}


class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
        // write your code here
           ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.size() == 0) return res;
        permuting(nums, new boolean[nums.size()], new ArrayList<Integer>(), res);
        return res;
    }
    
    private void permuting(ArrayList<Integer> nums, boolean[] visited, ArrayList<Integer> subList,  ArrayList<ArrayList<Integer>> res){
        if(subList.size() == nums.size()){
            res.add(new ArrayList<Integer>(subList));
            return;
        }
        HashSet<Integer> set = new  HashSet<Integer>();
        for(int i = 0; i < nums.size(); i++){
            if(set.contains(nums.get(i))) continue;
            if(!visited[i]){
                set.add(nums.get(i));
                subList.add(nums.get(i));
                visited[i] = true;
                permuting(nums, visited, subList, res);
                visited[i] = false;
                subList.remove(subList.size()-1);
            }
        }
    }

}