Thursday, August 28, 2014

Leetcode: Permutation

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].

Understand the problem:
The problem gives a collection of numbers, ask for returning all possible permutations. 
For an array with length n, the number of possible permutations n! 

Recursive Solution:
It is not hard to think of a recursive solution. 

Code (Java):
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        permute(num, 0, result);
        
        return result;
    }
    
    private void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
            result.add(temp);
        }
        
        for (int i = start; i < num.length; i++) {
            swap(num, start, i);
            permute(num, start + 1, result);
            swap(num, start, i);
        }
    }
    
    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) {
        int len = num.length;
        ArrayList<Integer> temp = new ArrayList<Integer>(len);
        for (int i = 0; i < len; i++) {
            temp.add(num[i]);
        }
        return temp;
    }
}


Summary:
The crux of this problem is using recursion. This problem is very similar to the palindrome partition. The only trick is to swap the number and swap them back. 

No comments:

Post a Comment