第七章 回溯算法 part04
491.递增子序列
题目链接/文章讲解
本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。
思路
cr:代码随想录
- 不能像原来的思路一样排序，因为原数组{4，7，6，7}排序后是{4，6，7，7}，成了一个递增子序列，但实际上没有这个子序列
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
if (path.size() > 1) { //符合收获结果的条件
result.add(new ArrayList<>(path));
// 进入子集就要收获结果。注意这里不要加return，要取树上的节点
}
Set<Integer> usedSet = new HashSet<>(); // 使用set对本层元素进行去重
for (int i = startIndex; i < nums.length; i++) {
if ((!path.isEmpty() && nums[i] < path.get(path.size() - 1))
|| usedSet.contains(nums[i])) { //小于分支右边也应该砍掉
continue;
}
usedSet.add(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了，这里的used数组仅记录本层
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> findSubsequences(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 7, 7};
List<List<Integer>> subsequences = solution.findSubsequences(nums);
System.out.println(subsequences); // 输出子序列
}
}
用数组来做哈希的解法：
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
if (path.size() > 1) {
result.add(new ArrayList<>(path));
}
boolean[] used = new boolean[201]; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
for (int i = startIndex; i < nums.length; i++) {
if ((!path.isEmpty() && nums[i] < path.get(path.size() - 1))
|| used[nums[i] + 100]) {
continue;
}
used[nums[i] + 100] = true; // 记录这个元素在本层用过了，本层后面不能再用了
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> findSubsequences(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
}
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex){
if(path.size() > 1){
result.add(new ArrayList<>(path));
}
Set<Integer> usedSet = new HashSet<>();
for(int i = startIndex; i < nums.length; i++){
if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || usedSet.contains(nums[i])) continue; //注意这里的条件
usedSet.add(nums[i]);
path.add(nums[i]);
backtracking(nums, i+1);
path.remove(path.size()-1); //remove队尾而不是直接num[i]
}
}
public List<List<Integer>> findSubsequences(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
}
46.全排列
题目链接/文章讲解
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
思路
cr：代码随想录
- 数组{1，2，3}，used数组依然是1记录用过，0记录未使用
- 排列可以重复取数
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, boolean[] used) {
// 此时说明找到了一组
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) { //这里是从0开始，以前是用startIndex避免取前面的数重复，但是排列是每一次都从头开始取
if (used[i]) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.add(nums[i]);
backtracking(nums, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
result.clear();
path.clear();
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return result;
}
}
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] nums, boolean[] used){
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i]) continue; //注意这里的条件判断 path里已经收录的元素，直接跳过
path.add(nums[i]);
used[i] = true;
backtracking(nums, used);
used[i] = false;
path.remove(path.size()-1);
}
}
public List<List<Integer>> permute(int[] nums) {
result.clear();
path.clear();
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return result;
}
}
47.全排列 II
题目链接/文章讲解
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容： used[i - 1] == true 也行，used[i - 1] == false 也行
思路
cr：代码随想录
- 树层去重和树枝去重的区别
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, boolean[] used) {
// 此时说明找到了一组
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同一树枝 nums[i - 1] 使用过
// used[i - 1] == false，说明同一树层 nums[i - 1] 使用过
// 如果同一树层 nums[i - 1] 使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue; //注意是continue
}
if (!used[i]) {
used[i] = true;
path.add(nums[i]);
backtracking(nums, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
result.clear();
path.clear();
Arrays.sort(nums); // 这里记得排序
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return result;
}
如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
下面这三道题都非常难，建议大家一刷的时候 可以适当选择跳过。
因为 一刷 也不求大家能把这么难的问题解决，大家目前能了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。
时间不够没写，之后慢慢补上
332. 重新安排行程（可跳过）
51. N皇后（适当跳过）
题目链接/文章讲解
N皇后这道题目还是很经典的，一刷的录友们建议看看视频了解了解大体思路 就可以 （如果没时间本次就直接跳过） ，先有个印象，二刷的时候重点解决。
37. 解数独（适当跳过）
题目链接/文章讲解
同样，一刷的录友们建议看看视频了解了解大体思路（如果没时间本次就直接跳过），先有个印象，二刷的时候重点解决。
总结
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html
