Leetcode–Permutations

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. In each iteration, add the next number in array to the existing list in result, insert at all possible locations.
  2. Use a linked list to easily insert new number at a given location.

Java Solution:

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num.length==0)return result;
        
        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]);
                    temp.add(newone);
                }
            }
            result = temp;
        }
        return result;
        
    }
}
Advertisements

One thought on “Leetcode–Permutations

  1. Pingback: Leetcode–Permutations II | Linchi is coding

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