Permutations II

To remove the duplicate result, first sort the array, so that same element is next to each other. Then when you have tried some value at one place, skip all the other same value at the same place because they will ended up with same result. Use a hashset to store all the used value

The rest is the same as the permutation without duplicate

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        for (int i = 0; i < num.length; i++) {
            tmp.add(num[i]);
        }
        return permutation(tmp);
    }
    
    public ArrayList<ArrayList<Integer>> permutation(ArrayList<Integer> list) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (list.size() == 1) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(list.get(0));
            res.add(tmp);
            return res;
        }
        HashSet<Integer> visited = new HashSet<Integer>();
        for (int i = 0; i < list.size(); i++) {
            int curr = list.get(i);
            if (!visited.contains(curr)) { // to skip duplicate result
                list.remove(i);
                for (ArrayList<Integer> l : permutation(list)) {
                    l.add(0, curr);
                    res.add(l);
                }
                list.add(i, curr); // put removed element back
                visited.add(curr);
            }
        }
        return res;
    }
}

Follow up: How many different permutation you can have if duplication presents. i.e. abb -> abb, bab, bba total 3

The general idea is like this: first we calculate the number of duplicates x1, x2….xn, Then among n positions, we pick x1 positions for element of x1 among n positions C(x1, n), then in the rest of the locations, we pick x2 positions for elements of x2, C(X2, n-x1). The result is C(x1,n)*C(x2, n-x1) * … * C(Xn, n-x(n-1)-…-x1) =
P(n, 0)/(P(x1)P(x2)…P(xn)).