力扣46. 全排列
力扣46. 全排列
原题，题目描述：
思路
经典的回溯题，给一个列表，需要做一个这个列表的全排列。思路就是递归。我们这么思考，比如给列表 [1,2,3]，我们使用递归，首先在第一次调用时就已经将元素 1 保留在了函数中，就可以将元素 [2,3]传入下一次调用，以此类推，再在每个函数中加入循环去遍历元素。比如第一次我第一次调用函数传的是元素 1 ，第二次我使用循环传递的是 2 ，第三次是 3 ，进入下一个函数后两个数字又以此类推的循环递归。由此得到 6 个排列结果。
当然这里有个问题，比如我们第一个函数传入元素 2 ，那我们如何在第二次调用函数的时候知道第一次是 2 ？我们可以将元素 2 和元素 1 交换位置，总是在第一个函数中使用数组的第一个元素就可以解决这个问题，逐渐缩短数组。
代码
下面是代码：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
if (len == 1) {
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[0]);
res.add(list);
return res;
}
int[] t = new int[len];
for (int i = 0; i < len; i++) {
System.arraycopy(nums, 0, t, 0, len);
int temp = t[0];
t[0] = t[i];
t[i] = temp;
List<List<Integer>> lists = permute2(t);
for (List<Integer> list : lists) {
list.add(t[0]);
}
res.addAll(lists);
}
return res;
}
public List<List<Integer>> permute2(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (1 == len - 1) {
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[1]);
res.add(list);
return res;
}
int[] t = new int[len - 1];
for (int i = 0; i < len - 1; i++) {
System.arraycopy(nums, 1, t, 0, len - 1);
int temp = t[0];
t[0] = t[i];
t[i] = temp;
List<List<Integer>> lists = permute2(t);
for (List<Integer> integers : lists) {
integers.add(t[0]);
}
res.addAll(lists);
}
return res;
}
}
时间复杂度应该是O(n\times n!)，空间复杂度O(n)，提交打败百分之97
力扣46. 全排列
https://www.than.pw/archives/%E5%8A%9B%E6%89%A346.-%E5%85%A8%E6%8E%92%E5%88%97