全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序*返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路：
采用递归，核心思想如：需要将[1,2,3]全排列，拆分成两部分，第一个数字和剩下的数字，在这里，可以拆分为1 和2 3，2 和 1 3，3 和1 2。则[1,2,3]的全排列相当于 1加上[2,3]的全排列，即[2,3],[3,2]，最终以1开头的结果为[1,2,3]和[1,3,2]，剩下的数字类似，最终把分别以1,2,3开头的全排列加起来就是所有排列结果。整体思路就是这样，能力不足，不太容易用更通俗的语言和原理来解释，只能通过例子来解释。
代码：
未优化版本：
时间和空间复杂度都很高。。。。
// 交换数组中两个数
public void swap(int[] list, int idx1, int idx2) {
int tmp = list[idx1];
list[idx1] = list[idx2];
list[idx2] = tmp;
}
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0)
return null;
List<List<Integer>> perList = new ArrayList<>();
List<Integer> per = new ArrayList<>();
if (nums.length == 1) {
per.add(nums[0]);
perList.add(per);
return perList;
}
// 遍历以每个数字作为首字母的排列
for (int j = 0; j < nums.length; j++) {
swap(nums, 0, j);
List<List<Integer>> tmp = permute(Arrays.copyOfRange(nums, 1,nums.length));
for (List<Integer> i : tmp) {
per = new ArrayList<>();
per.add(nums[0]);
per.addAll(i);
perList.add(per);
}
swap(nums, j, 0);
}
return perList;
}
优化版本：
public void backTrace(int first, List<Integer> out, List<List<Integer>> res,int len){
if (first == len) {
res.add(new ArrayList<>(out));
return;
}
for (int i = first; i < len; i++) {
Collections.swap(out, i, first);
backTrace(first + 1,out, res, len);
Collections.swap(out, first, i);
}
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> perList = new ArrayList<>();
List<Integer> out = new ArrayList<>();
for (int i : nums) {
out.add(i);
}
backTrace(0, out,perList, nums.length);
return perList;
}
这是参照题解写的代码（虽然基本上和题解一模一样了），看了这个代码后分析了一下自己前面写的代码存在的问题。 我前面是通过nums来在递归过程中生成一个个List<Integer>，再通过addAll方法一个个添加进上一级递归的结果中。。。现在看来这样的方法真的很蠢，浪费了很多空间不说，时间也用了很多。还有就是我之前是通过交换nums里面的元素再添加进List<Integer>中，其实这完全可以合并成一步：先把nums的全部元素添加进一个List中，然后只需要不断递归交换里面的元素就行了。这样就剩下了很多中间产生的List，还节约了时间。