当前位置：首页 > news >正文

回溯进阶（一）：以全排列问题为例，来展示如何对回溯的纵向和横向进行操作

news 2025/5/11 11:05:50

对回溯的更深层理解：

对回溯和递归有了更深一层的了解，知晓了：

在循坏外面为横向一层都可以保留的
在循环内部为纵向一层都可以保留的；
需要回滚的是循环内部的，即纵向的。

全排列1：（不重复）

链接：

https://leetcode.cn/problems/permutations/description/

题目：

方法一：

class Solution {public List<List<Integer>> ans=new ArrayList<>();public List<Integer> com=new ArrayList<>();public List<List<Integer>> permute(int[] nums) {int n=nums.length;traceBack(nums);return ans;}public void traceBack(int[] nums){if(com.size()==nums.length){ans.add(new ArrayList(com));return;}for(int i=0;i<=nums.length;i++){if(com.contains(nums[i])) continue;com.add(nums[i]);traceBack(nums);com.remove(com.size()-1);}}
}

解释：

ans表示答案，是每一个排列的集合；
com表示每一个不同的排列；
都从头开始遍历，如果在纵向中出现过一次，那么就舍去出现过的。即 if(com.contains(nums[i])) continue;

方法二（开辟额外数组记录状态）

class Solution {public List<Integer> com=new ArrayList<>();public List<List<Integer>> ans=new ArrayList<>();public List<List<Integer>> permute(int[] nums) {int n=nums.length;boolean[] used=new boolean[n];traceBack(nums,used);return ans;}public void traceBack(int[] nums,boolean[] used){if(com.size()==nums.length){ans.add(new ArrayList(com));return ;}for(int i=0;i<nums.length;i++){if(used[i]==true) continue;com.add(nums[i]);used[i]=true;traceBack(nums,used);used[i]=false;com.remove(com.size()-1);}}
}

解释：

ans表示答案，是每一个排列的集合；
com表示每一个不同的排列；
usde表示第i个是否被使用过；
都从头开始遍历，如果在纵向中出现过一次，那么就舍去出现过的。我们用used数组来记录，出现过就使used[i]==true，回滚使也要把used[i]给还原了。

全排列2：（可以重复）

题目：

链接：

https://leetcode.cn/problems/permutations-ii/description/

全排列2中为什么要去去重：

如图所示，第一行中的第一个1和第2个1，最终的结果一样，所以第二个1就没有存在的必要了。

在第一行中的元素2，他的下一行，有两个一样的1，这样也会使结果一样，所以第二个1没有存在的必要

方法一（使用.contains()来判断是否重复）：

class Solution {public List<Integer> com=new ArrayList<>();public List<List<Integer>> ans=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {int n=nums.length;boolean[] used=new boolean[n];traceBack(nums,used);return ans;}public void traceBack(int[] nums,boolean[] used){if(com.size()==nums.length){if(!ans.contains(new ArrayList(com))){ans.add(new ArrayList(com));}return ;}for(int i=0;i<nums.length;i++){if(used[i]==true) continue;com.add(nums[i]);used[i]=true;traceBack(nums,used);used[i]=false;com.remove(com.size()-1);}}
}

解释：

ans表示答案，是每一个排列的集合；
com表示每一个不同的排列；
used表示第i个是否被使用过；
都从头开始遍历，如果在纵向中出现过一次，那么就舍去出现过的。我们用used数组来记录，出现过就使used[i]==true，回滚使也要把used[i]给还原了。
使用ans.contains(）来判断，重复就直接return；

这种方法能写，但是非常的低效，不推荐；

方法二（在循环外面创建新的辅助状态）：

class Solution {public List<Integer> com=new ArrayList<>();public List<List<Integer>> ans=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {int n=nums.length;boolean[] used=new boolean[n];traceBack(nums,used);return ans;}public void traceBack(int[] nums,boolean[] used){if(com.size()==nums.length){ans.add(new ArrayList(com));return ;}boolean[] used2=new boolean[21];//在循环外代表每一行，循环内代表每一列。//这个used2的意思是：如果在同一分支中有相同的数字，那么必然重复，所以就直接剪枝即可。for(int i=0;i<nums.length;i++){if(used2[nums[i]+10]) continue;if(used[i]) continue;used2[nums[i]+10]=true;used[i]=true;com.add(nums[i]);traceBack(nums,used);used[i]=false;com.remove(com.size()-1);}}
}

解释：

ans表示答案，是每一个排列的集合；
com表示每一个不同的排列；
used表示第i个是否被使用过；
used2表示nums[i]这个数在横向中是否出现过，如果出现过就直接continue；

疑问点

为什么used2要开辟21的空间，为什么下标要nums[i]+10？

解释：因为题中的数据范围给出了nums[i]在-10到10的范围内，所以开辟21个空间，再+10是一种映射，使每一种情况都能表示；

那么就有帅气的同学问了，有没有更简洁高效的回溯方法来解决，有的兄弟，有的：

方法三（先排序，再记录横向上一个元素last来代替used2）

class Solution {public List<Integer> com=new ArrayList<>();public List<List<Integer>> ans=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {int n=nums.length;boolean[] used=new boolean[n];Arrays.sort(nums);traceBack(nums,used);return ans;}public void traceBack(int[] nums,boolean[] used){if(com.size()==nums.length){ans.add(new ArrayList(com));return ;}int last=6666;// boolean[] used2=new boolean[21];//在循环外代表每一行，循环内代表每一列。//这个used2的意思是：如果在同一分支中有相同的数字，那么必然重复，所以就直接剪枝即可。for(int i=0;i<nums.length;i++){// if(used2[nums[i]+10]) continue;if(used[i]) continue;// used2[nums[i]+10]=true;if(last==nums[i]) continue;last=nums[i];used[i]=true;com.add(nums[i]);traceBack(nums,used);used[i]=false;com.remove(com.size()-1);}}
}