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