LeetCode Permutations II

Problem

Permutations I

First of all let's see the Permutations I. My code is a replica of an elegant, recursive solution on this post.

public class Solution {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        permuteHelper(num, 0);
        return ret;
    }

    public void permuteHelper(int[] num, int i) {
        if (i == num.length) {
            ArrayList<Integer> per = new ArrayList<Integer>();
            for (int k = 0; k < num.length; k++) {
                per.add(num[k]);
            }
            ret.add(per);
            return;
        }
        for (int j = i; j < num.length; j++) {
            swap(num, i, j);
            permuteHelper(num, i+1);
            swap(num, i, j);
        }
    }

    public void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}

Unique?

The challenge for Permutation II is to guarantee the uniqueness: the input integer for Permutations I are distinct thus we don't need to rule out duplicated permutations. But in this problem, we could come into difficulty.

My first naive solution is adding following conditional statement inside the for loop:

if (j != i && num[i] == num[j]) { 
    continue;
}

It seems to work on some cases but will fail on most situation. For example, it cannot rule out the duplicates for input {1, 2, 2}.

The reason

The cause could be less implicit if you look at the recursion tree generated by this algorithm:

permuteHelper(num, 1) could generate the same(which means duplicates) permutations when num = {2, 1, 2 and num = {2, 2, 1}.

The algorithm fixes the first ith elements and recursively permute the remaining n-i elements but when you make multiple recursive calls on the same first ith elements, you will get duplicate permutations.

Thus, the solution is to make sure that whenever you make a recursive call, the first ith elements are distinct against the first ith elements in other recursive calls.

We have the code and we can see the key difference resides in the usage of a hashset to avoid duplicated-first-ith-elements-recursive calls:

public class Solution {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        permuteHelper(num, 0);
        return ret;
    }

    public void permuteHelper(int[] num, int i) {
        if (i == num.length-1) {
            ArrayList<Integer> per = new ArrayList<Integer>();
            for (int k = 0; k < num.length; k++) {
                per.add(num[k]);
            }
            ret.add(per);
            return;
        }
        HashSet<Integer> hs = new HashSet<Integer>();
        for (int j = i; j < num.length; j++) {
            if (hs.contains(num[j])) {
                continue;
            }
            hs.add(num[j]);
            swap(num, i, j);
            permuteHelper(num, i+1);
            swap(num, i, j);
        }
    }

    public void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}