Leetcode–Permutations II

The Problem:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Notes:

  1. Solution 1 is just same as Permutations, with a hash set to check if the list is already in the result. Could directly use list.toString() and store the string in set to check for duplicates.
  2. Solution 2 I will add later…

Java Solution I:

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num.length==0)return result;
        
        HashSet<String> set = new HashSet<String>();
        List<Integer> first = new LinkedList<Integer>();
        first.add(num[0]);
        result.add(first);
        
        for(int i = 1; i < num.length; i++){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(int j = 0; j < result.size(); j++){
                List<Integer> one = result.get(j);
                for(int k = 0; k <= one.size(); k++){
                    List<Integer> newone = new LinkedList<Integer>(one);
                    newone.add(k, num[i]);
                    if(!set.contains(newone.toString())){
                        temp.add(newone);
                        set.add(newone.toString());
                    }
                }
            }
            result = temp;
        }
        return result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s