Given a collection of distinct 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], [3,2,1] ]

题目：给定一个数组，列出所有的排列方式。

思路：用递归，当数组为{1}，只有一种排列方式；当为{1，2}时，在{1}的基础上把2插入，可得到{1，2}，{2，1}；当数组为{1，2，3}时，把3插入前面的两个数组，一次类推。不过感觉自己的代码有点繁琐。

public List<List<Integer>> permute(int[] nums){ List<List<Integer>> list1 = new ArrayList<List<Integer>>(); if(nums.length == 1) { List<List<Integer>> list = new ArrayList<List<Integer>>(); List<Integer> l = new ArrayList<Integer>(); l.add(nums[0]); list.add(l); return list; } int[] num1 = Arrays.copyOfRange(nums, 1, nums.length); int n = nums[0]; for(List<Integer> li : permute(num1)) { int[] num = listToArray(li); list1.addAll(sort(num, n)); } return list1; } public List<List<Integer>> sort(int[] nums, int num){//前一个数组，及即将插入的数，得到新的组合数是前一个数组长度+1 List<List<Integer>> list = new ArrayList<List<Integer>>(); for(int i = 0; i < nums.length+1;i++) { int[] n = new int[nums.length+1]; for(int k = 0 ; k < nums.length;k++) {//每次都要重置数组。 n[k] = nums[k]; } int tmp = n[i]; n[i] = num; int j = n.length-1; for(;j > i+1;j--) { n[j] = n[j-1]; } if(i != j) { n[j] = tmp; } list.add(arrayToList(n)); } return list; } public int[] listToArray(List<Integer> list){ int[] n = new int[list.size()]; int j = 0; for(Integer i:list){ n[j++] = i; } return n; } public List<Integer> arrayToList(int[] nums) { List<Integer> list = new ArrayList<Integer>(); for(int i = 0;i < nums.length;i++){ list.add(nums[i]); } return list; }

简洁的思路：一个一个取出来就行了

public List<List<Integer>> permute(int[] num) { int len = num.length; if (len == 0) return ret; List<Integer> list = new ArrayList<Integer>(); run(list, num); return ret; } public void run(List<Integer> list, int[] num) { if (list.size() == num.length) { //注意这里要重新new一个list，要不然后面会被修改 List<Integer> res = new ArrayList<Integer>(); res.addAll(list); ret.add(res); return; } for (int i = 0; i < num.length; i++) { if (list.contains(num[i])) { continue; } list.add(num[i]); run(list, num); list.remove(list.indexOf(num[i])); //不要忘记这一步 } }

15日更新：今天吃完饭谷歌了一下，找到一种新的解法，感觉自己绝不会想到这样的解法，在这里贴出来

public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); <span style="white-space:pre"> </span> //start from an empty list result.add(new ArrayList<Integer>());//reslut里面先放一个空的list<Integer>对象 for (int i = 0; i < num.length; i++) {//开始选择元素 //list of list in current iteration of the array num ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>(); <span style="white-space:pre"> </span> for (ArrayList<Integer> l : result) {//遍历result中存在的元素List<Integer> // # of locations to insert is largest index + 1 for (int j = 0; j < l.size()+1; j++) {//根据List<Integer>里元素来放，每个位置都放一边 // + add num[i] to different locations l.add(j, num[i]);//先放j=0位置 ArrayList<Integer> temp = new ArrayList<Integer>(l); current.add(temp);//放完之后存入current //System.out.println(temp); // - remove num[i] add//存好之后删除这个元素，进行下一个位置摆放 l.remove(j); } } result = new ArrayList<ArrayList<Integer>>(current);//一轮放完之后存到result中 } return result; }

种一棵树最好的时间是十年前，其次是现在！