代码随想录-算法训练营day29【回溯算法05：递增子序列、全排列】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第七章 回溯算法part05* 491.递增子序列
* 46.全排列
* 47.全排列 II详细布置 491.递增子序列 本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。 
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v  46.全排列 
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex 
https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html   
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W  47.全排列 II 
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行 https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html     视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ

目录

0491_递增子序列

0046_全排列

0047_全排列II

---

0491_递增子序列

在 Java 中，indexOf 和 get 是用于访问集合类（如列表）元素的两种不同方法。

1. indexOf: indexOf 方法用于查找列表中特定元素的索引位置。它接受一个对象作为参数，并返回该对象在列表中第一次出现的索引位置。如果列表中不存在该对象，则返回 -1。这个方法在 List 接口中定义。

2. get: get 方法用于获取列表中指定索引位置的元素。它接受一个整数参数（索引），并返回该索引位置上的元素。这个方法也在 List 接口中定义。

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;import java.util.*;public class _0491_递增子序列 {
}class Solution0491 {//超时！List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTrack(nums, 0);return res;}private void backTrack(int[] nums, int startIndex) {if (check(path)) {res.add(new ArrayList<>(path));}for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);backTrack(nums, i + 1);path.removeLast();}}private boolean check(LinkedList<Integer> list) {if (list.size() <= 1 || res.contains(list)) {return false;}boolean flag = true;for (int i = 1; i < list.size(); i++) {if (list.get(i - 1) > list.get(i)) {flag = false;break;}}return flag;}
}class Solution0491_2 {//通过ChatGPT修改，不超时了。使用set去重！List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();Set<List<Integer>> set = new HashSet<>();//使用哈希集合来存储已经存在的路径public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return res;}private void backTracking(int[] nums, int startIndex) {if (path.size() >= 2) {if (check(path) && !set.contains(path)) {//使用哈希集合进行快速查找res.add(new ArrayList<>(path));set.add(new ArrayList<>(path));//将当前路径添加到哈希集合中}}for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);backTracking(nums, i + 1);path.removeLast();}}private boolean check(List<Integer> path) {for (int i = 0; i < path.size() - 1; i++) {if (path.get(i) > path.get(i + 1)) {return false;}}return true;}
}class Solution0491_3 {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex) {if (path.size() >= 2)result.add(new ArrayList<>(path));HashSet<Integer> hs = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i]))continue;hs.add(nums[i]);path.add(nums[i]);backTracking(nums, i + 1);path.remove(path.size() - 1);}}
}class Solution0491_4 {private List<Integer> path = new ArrayList<>();private List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return res;}private void backtracking(int[] nums, int start) {if (path.size() > 1) {res.add(new ArrayList<>(path));}int[] used = new int[201];for (int i = start; i < nums.length; i++) {if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||(used[nums[i] + 100] == 1)) continue;used[nums[i] + 100] = 1;path.add(nums[i]);backtracking(nums, i + 1);path.remove(path.size() - 1);}}
}class Solution0491_5 {//法二：使用mapList<List<Integer>> res = new ArrayList<>();//结果集合LinkedList<Integer> path = new LinkedList<>();//路径集合public List<List<Integer>> findSubsequences(int[] nums) {getSubsequences(nums, 0);return res;}private void getSubsequences(int[] nums, int start) {if (path.size() > 1) {res.add(new ArrayList<>(path));//注意这里不要加return，要取树上的节点}HashMap<Integer, Integer> map = new HashMap<>();for (int i = start; i < nums.length; i++) {if (!path.isEmpty() && nums[i] < path.getLast()) {continue;}//使用过了当前数字if (map.getOrDefault(nums[i], 0) >= 1) {continue;}map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);path.add(nums[i]);getSubsequences(nums, i + 1);path.removeLast();}}
}

0046_全排列

//解法2：通过判断path中是否存在数字，排除已经选择的数字
class Solution0046_3 {}

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class _0046_全排列 {
}class Solution0046 {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {backTrack(nums, 0);return res;}private void backTrack(int[] nums, int startIndex) {if (startIndex == nums.length) {res.add(new ArrayList<>(path));return; //结束当前递归，避免继续递归时越界}for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);swap(nums, i, startIndex); //将当前位置的数字与起始位置的数字交换backTrack(nums, startIndex + 1); //递归进入下一层swap(nums, i, startIndex); //恢复原数组，以便进行下一次迭代path.removeLast();}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}class Solution0046_2 {List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();//用来存放符合条件结果boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0) {return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}//解法2：通过判断path中是否存在数字，排除已经选择的数字
class Solution0046_3 {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {if (nums.length == 0) return result;backtrack(nums, path);return result;}public void backtrack(int[] nums, LinkedList<Integer> path) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));}for (int i = 0; i < nums.length; i++) {//如果path中已有，则跳过if (path.contains(nums[i])) {continue;}path.add(nums[i]);backtrack(nums, path);path.removeLast();}}
}

0047_全排列II

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class _0047_全排列II {
}class Solution0047 {List<List<Integer>> result = new ArrayList<>();//存放结果List<Integer> path = new ArrayList<>();//暂存结果public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backTrack(nums, used);return result;}private void backTrack(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] == false) {continue;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] == false) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复used[i] = false;//回溯}}}
}class Solution0047_2 {boolean[] vis;public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> perm = new ArrayList<Integer>();vis = new boolean[nums.length];Arrays.sort(nums);backtrack(nums, ans, 0, perm);return ans;}public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {if (idx == nums.length) {ans.add(new ArrayList<Integer>(perm));return;}for (int i = 0; i < nums.length; ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}perm.add(nums[i]);vis[i] = true;backtrack(nums, ans, idx + 1, perm);vis[i] = false;perm.remove(idx);}}
}