Thursday, August 28, 2014

Leetcode: Permutation 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].

Understand the problem:
The problem is an extension to Permutation I, the mainly difference is it exists the duplicated elements, and we return only unique permutations. 

The solution is very similar to the permutation I, the only difference is before we swap the number start and i, we check if between start and i has duplicates. If yes, it indicates that we visited the number before, so simply jump to next iteration.

Code (Java):
public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        permuteUnique(num, 0, result);
        return result;
    private void permuteUnique(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
        for (int i = start; i < num.length; i++) {
            if (!containsDup(num, start, i)) {
                swap(num, i, start);
                permuteUnique(num, start + 1, result);
                swap(num, i, start);
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    private ArrayList<Integer> toArrayList(int[] num) {
        ArrayList<Integer> temp = new ArrayList<Integer>(num.length);
        for (int i = 0; i < num.length; i++) {
        return temp;
    private boolean containsDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        return false;

Note the method on how to determine the duplicates. This the most tricky part of this problem.

Update on 10/27/14:

No comments:

Post a Comment