Question:
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].
Solution:
Using the idea of Queue Jumping。
public class Solution { public List<List<Integer>> permute(int[] num) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(num == null || num.length == 0){ return result; } return getPer(num,0); } public List<List<Integer>> getPer(int[] num, int index){ List<List<Integer>> result = new ArrayList<List<Integer>>(); if(index == num.length-1){ List<Integer> newRes = new ArrayList<Integer>(); newRes.add(num[index]); result.add(newRes); return result; } result = getPer(num, index+1); List<List<Integer>> result2 = new ArrayList<List<Integer>>(); for(List<Integer> element : result){ List<Integer> newRes; for(int i =0; i<=element.size(); i++){ newRes = new ArrayList<Integer>(); newRes.addAll(element); newRes.add(i,num[index]); result2.add(newRes); } } return result2; } }