46. 全排列 - 力扣（LeetCode）

法1：暴力枚举

总共n!种全排列，一一列举出来放入list就行，关键是怎么去枚举呢？那就每次随机取一个，然后删去这个，再从剩下的数组中继续去随机选一个，依次类推直到为数组为0。

为了快，选择set，每选了一个，set里就删除一个，再继续从里面随机选。

Tip:int[]转换为set，利用stream流替代传统for循环

class Solution {List<List<Integer>> ans = null;public List<List<Integer>> permute(int[] nums) {ans = new ArrayList<List<Integer>>();//记录还未抽中的数组元素,技巧：用stream流代替传统循环Set<Integer> set = new HashSet<>(Arrays.stream(nums).boxed().toList());int n = nums.length;bruteForce(set, n, new ArrayList<>(n));return ans;}//n表示set还剩几个元素没抽，list表示这次随机抽取的全排列public void bruteForce(Set<Integer> set, int n, List<Integer> list) {//反正就剩最后一个了，不用随机抽了//不用0，是为了减少一次拷贝if(n == 1) {for(int num:set)list.add(num);ans.add(list);return;}for(int num:set) {//需要拷贝构造新的list和setList<Integer> newList = new ArrayList<>(list);newList.add(num);Set<Integer> newSet = new HashSet<>(set);newSet.remove(num);bruteForce(newSet, n - 1, newList);}}
}

本来枚举共n!个，bruteForce()方法本身只调用了n!（1*n*n-1*...*2）次，但因为每次要拷贝新的list和set（list和set加起来共n个元素），所以每次调用bruteForce前拷贝都需要O(n)，所以算上拷贝时间复杂度公式应该为

具体为多少，GPT说为O(n⋅n!)我不知道对不对...不会算...

很明显这样暴力枚举的话，中间变量，list和set很多，拷贝也花时间。所以才有了回溯算法进行优化。

法2：回溯

可以不拷贝list，而是先添加，遍历完这次排列后，再删除回溯复原，再开始下一个，这就是所谓的回溯吧。

注意每次最后要添加list的拷贝。不过new ArrayList<>(originArr)是浅拷贝，里面的每个属性仍指向同一个对象，不过这里无所谓，不需要深拷贝，本身Integer包装类也是不可变对象。

class Solution {List<List<Integer>> ans = null;public List<List<Integer>> permute(int[] nums) {ans = new ArrayList<List<Integer>>();//记录还未抽中的数组元素,技巧：用stream流代替传统循环Set<Integer> set = new HashSet<>(Arrays.stream(nums).boxed().toList());int n = nums.length;bruteForce(set, n, new ArrayList<>(n));return ans;}//n表示set还剩几个元素没抽，list表示这次随机抽取的全排列public void bruteForce(Set<Integer> set, int n, List<Integer> list) {//没了if(n == 0) {//这里添加的应是新的拷贝,不然所有添加的都是同一个list了ans.add(new ArrayList<Integer>(list));return;}Set<Integer> tmpSet = new HashSet<>(set);for(int num:tmpSet) {list.add(num);set.remove(num);bruteForce(set, n - 1, list);//然后回溯list.remove(list.size()-1);set.add(num);}}
}

但我这种还是得拷贝set来方便后面继续抽未选中过的。不够优化。

官解十分巧妙利用了list的未排列部分来作set，这样可以每次选择list的未排列部分作为下一个排列的 来替代 从set中选择下一个排列的，然后通过回溯复原。

class Solution {List<List<Integer>> ans = null;public List<List<Integer>> permute(int[] nums) {ans = new ArrayList<List<Integer>>();//stream流代替传统for循环List<Integer> list = new ArrayList<>(Arrays.stream(nums).boxed().toList());int n = nums.length;backTrack(list, n, 0);return ans;}//n表示总共多少个元素，arrangedN表示已经排好多少个了,同时也表示list下一个应该排的下标public void backTrack(List<Integer> list, int n, int arrangedN) {//没了if(arrangedN == n) {//这里添加的应是新的拷贝,不然所有添加的都是同一个list了ans.add(new ArrayList<Integer>(list));return;}for(int i = arrangedN; i<n;i++) {Collections.swap(list, arrangedN, i);backTrack(list, n, arrangedN+1);//回溯复原Collections.swap(list, arrangedN, i);}}
}