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. 

Solution:
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);
            result.add(temp);
            return;
        }
        
        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++) {
            temp.add(num[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;
    }
}

Discussion:
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