回溯算法之组合和排列结果如何去重
回溯算法之组合和排列结果如何去重
回溯算法中有两个难点：一是剪枝，二是去重。
剪枝是指在回溯搜索过程中，根据一定的条件判断，提前终止某些不可能产生最优解或有效解的搜索分支，从而减少搜索量，提高算法效率。
去重指在回溯算法生成所有可能解的过程中，去除重复的解，确保最终结果集中的每个解都是唯一的。
先来讲解去重的思路：
排序 + 标记
先对输入的数组进行排序，这样相同的元素会相邻。在回溯过程中，使用一个标记数组来记录每个元素是否已经被使用过。当遇到相同元素时，如果该元素的前一个相同元素没有被使用过，那么当前元素就不能使用，否则会产生重复组合。
接下来通过两道题来帮助理解如何去重。
组合去重
题目来自于力扣
问题描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8，
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5，
输出:
[
[1,2,2],
[5]
]
class Solution {
public List<List<Integer>> res = new ArrayList<>();
public ArrayList<Integer> path = new ArrayList<>();
public boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.sort(candidates);
Arrays.fill(used,false);
backTracking(candidates,target,0,0);
return res;
}
public void backTracking(int[] candidates,int target,int sum,int startIndex){
if(sum > target){
return;
}
if(sum == target){
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i < candidates.length;i++){
if(i > 0 && candidates[i] == candidates[i-1] && !used[i-1]){
continue;
}
used[i] = true;
path.add(candidates[i]);
sum += candidates[i];
backTracking(candidates,target,sum,i+1);
used[i] = false;
path.remove(path.size()-1);
sum -= candidates[i];
}
}
}
这题的代码中最关键的是 used 数组和 for 循环中的 if 判断：
if(i > 0 && candidates[i] == candidates[i-1] && !used[i-1]){
continue;
}
以示例1为例，找出和为8的组合。首先需要对数组中的数进行排序，这个很重要！！！排序完成之后，两个1都在最前面，可以看到对第一个1回溯得到的结果就已经得到了我们想要的结果，因此对第二个1在进行一次回溯就没必要了。因此
i > 0 && candidates[i] == candidates[i-1]
就是跳过当前下标的值等于前一个下标值的情况。
我们来看另一个条件
!used[i-1]，used 数组是为了辨别当前下标的值有没有被使用。使用过就是 true，没有就是 false
如果没有 !used[i-1] 这个条件，那么在进行回溯的时候，就会跳过 [1,1,6] 这个组合了
我们在第一次遍历到1时，就已经将对应 used 下标改为 true 了，这样我们在下面进行回溯的时候，就不会跳过了
排列去重
题目来自于力扣
问题描述：
给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
这一题要比上一题简单一些，上面一题多了一个和等于 target 的条件。这题去重就可以了
class Solution {
public List<List<Integer>> res = new ArrayList<>();
public List<Integer> path = new ArrayList<>();
public boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
Arrays.fill(used, false);
backTracking(nums);
return res;
}
public void backTracking(int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
backTracking(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
}
res用于存储最终的全排列结果path用于存储路径上的结果used是一个布尔数组，用于标记数组nums中的每个元素是否已经在当前排列中被使用过。
这题的关键在于这部分代码：
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
backTracking(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
由于这是排列，如果元素未被使用过（!used[i]），才将其添加到 path 中，并标记为已使用（used[i] = true），然后递归调用 backTracking 方法继续生成排列。递归返回后，需要进行回溯操作，将该元素从 path 中移除，并将其标记为未使用（used[i] = false），以便尝试其他可能的排列。