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].
Analysis:
![[Leetcode]-- Permutations](http://1.bp.blogspot.com/-eK9ZsXb3Qeg/UXgusEhFfoI/AAAAAAAAAOs/99btdWK1KSw/s1600/NewPermutation.gif "[Leetcode]-- Permutations")
The idea of this classic problem is to use
backtracking.
We want to get permutations, which is mainly about
swap values in the list.
Consider:
a -->
a
ab --> ab, ba
abc --> abc, acb, bac,
bca, cab, cba.
...
where for the length of n,
the permutations can be generated by
(1) Swap the 1st element
with all the elements, including itself.
(2) Then the 1st element is fixed, go to the next
element.
(3) Until the last element
is fixed. Output.
It‘s more clear in the figure above. The key
point is to make the big problem into smaller problem, here is how to convert
the length n permutation into length n-1 permutation problem.
public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] num) { int len = num.length; ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); permutation(num, 0, len, result); return result; } public void permutation (int[] num, int depth, int len, ArrayList<ArrayList<Integer>> result){ if(depth == len) { ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0; i < len; i++){ list.add(num[i]); } result.add(list); } for(int i = depth; i< len; i++){ int tmp = num[i]; num[i] = num[depth]; num[depth] = tmp; permutation(num, depth + 1, len, result); tmp = num[i]; num[i] = num[depth]; num[depth] = tmp; } } }