描述的很简单，就是给定几个数，然后输出他们所有排列的可能。
解法一 插入
这是自己开始想到的一个方法，考虑的思路是，先考虑小问题怎么解决，然后再利用小问题去解决大问题。没错，就是递归的思路。比如说，
如果只有 1 个数字 [ 1 ]，那么很简单，直接返回 [ [ 1 ] ] 就 OK 了。
如果加了 1 个数字 2， [ 1 2 ] 该怎么办呢？我们只需要在上边的情况里，在 1 的空隙，也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。
如果再加 1 个数字 3，[ 1 2 3 ] 该怎么办呢？同样的，我们只需要在上边的所有情况里的空隙里插入数字 3 就行啦。例如 [ 2 1 ] 在左边，中间，右边插入 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 ], [ 3 1 2 ]，[ 1 3 2 ]，[ 1 2 3 ] ]。
如果再加数字也是同样的道理，只需要在之前的情况里，数字的空隙插入新的数字就够了。
思路有了，直接看代码吧。
publicList<List<Integer>>permute(int[] nums) { returnpermute_end(nums,nums.length-1); } // end 表示当前新增的数字的位置privateList<List<Integer>>permute_end(int[] nums, intend) { // 只有一个数字的时候if(end==0){ List<List<Integer>>all=newArrayList<>(); List<Integer>temp=newArrayList<>(); temp.add(nums[0]); all.add(temp); returnall; } //得到上次所有的结果List<List<Integer>>all_end=permute_end(nums,end-1); intcurrent_size=all_end.size(); //遍历每一种情况for (intj=0; j<current_size; j++) { //在数字的缝隙插入新的数字for (intk=0; k<=end; k++) { List<Integer>temp=newArrayList<>(all_end.get(j)); temp.add(k, nums[end]); //添加到结果中all_end.add(temp); }; } //由于 all_end 此时既保存了之前的结果，和添加完的结果，所以把之前的结果要删除for (intj=0; j<current_size; j++) { all_end.remove(0); } returnall_end; }
既然有递归的过程，我们也可以直接改成迭代的，可以把递归开始不停压栈的过程省略了。
publicList<List<Integer>>permute(int[] nums) { List<List<Integer>>all=newArrayList<>(); all.add(newArrayList<>()); //在上边的基础上只加上最外层的 for 循环就够了，代表每次新添加的数字for (inti=0; i<nums.length; i++) { intcurrent_size=all.size(); for (intj=0; j<current_size; j++) { for (intk=0; k<=i; k++) { List<Integer>temp=newArrayList<>(all.get(j)); temp.add(k, nums[i]); all.add(temp); } } for (intj=0; j<current_size; j++) { all.remove(0); } } returnall; }
时间复杂度，如果只分析代码的话挺复杂的。如果从最后的结果来说，应该是 n! 个结果，所以时间复杂度应该是 O（n！)。
空间复杂度：O（1）
总
这道题很经典了，用动态规划，回溯，递归各实现了一遍，当然解法一强行递归了一下，和解法三相比真是相形见绌，解法三才是原汁原味的递归，简洁优雅。
