lc46全排列——回溯
法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和set
List<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);
}
}
}原文地址：https://blog.csdn.net/qq_61587494/article/details/144377824
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！