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].
思路很简单，例如[1,2]的全排列为[1,2][2,1],那么[1,2,3]的全排列为在[1,2]所有全排列的每个排列插入3，[1,2]插入3有3种方式：[3,1,2][1,3,2][1,2,3]; [2,1]插入3也有3种方式:[3,2,1][2,3,1][2,1,3],取并集就能得到[1,2,3]的全排列为:[3,1,2][1,3,2][1,2,3][3,2,1][2,3,1][2,1,3].
由此可见，num[0]到num[n]的全排列等于num[0]到num[n-1]的全排列的每种排列插入num[n]后取并集即可。
代码中pre中存储num[0]到num[n-1]的全排列，cur中存储num[0]到num[n]的全排列，然后不断迭代。
public class Solution { public List<List<Integer>> permute(int[] nums) { int size = nums.length; List<List<Integer>> pre = new ArrayList<List<Integer>>(); pre.add(new LinkedList<Integer>()); for(int i=0;i<size;i++) { List<List<Integer>> cur = new ArrayList<List<Integer>>(); for(List<Integer>list :pre) { for(int j=0;j<=list.size();j++) { List<Integer> newlist = new LinkedList<Integer>(); newlist.addAll(list); newlist.add(j,nums[i]); cur.add(newlist); } } pre.clear(); pre.addAll(cur); } return pre; } }
原文：http://www.cnblogs.com/mrpod2g/p/4481305.html