第七章 回溯算法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
day29
非递减子序列
//关键在于不能排序,所以使用哈希法去重//树枝上收集结果而不是仅在子叶上,所以一进入回溯函数就收割结果,而且不return,继续往后延伸树枝//在for循环外面新建hashset或者hash数组,只管树层上的去重class Solution {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循环外面新建,只针对本层for循环不能出现重复元素,也就是只在本树层去重,进入下一层的时候used会更新,所以树枝不去重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 说明本树层上已经用过了,就不能用了;//如果是在树枝上,因为已经进入了新的回溯函数,所以nums已经重置了,used[nums[i] + 100] == 0,就可以加进去used[nums[i] + 100] = 1;//本层此数用过了path.add(nums[i]);backtracking(nums, i + 1);path.remove(path.size() - 1);}}}
全排列
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] used;//元素个数确定,数组也行,不对不行,要用path.size==nums.length去判断结束,只能用Listpublic List<List<Integer>> permute(int[] nums) {//子叶上收集,判断深度方向上结束后收割used = new int[nums.length];backtricking(nums,0);return result;}private void backtricking(int[] nums,int index){if(path.size() == nums.length) {result.add(new ArrayList(path));}for(int i=0;i<nums.length; i++){if(used[i] != 0 ) continue;used[i] = 1;path.add(nums[i]);index++;backtricking(nums,index);index--;path.remove(path.size() - 1);used[i]=0;}}}
全排列2
//只是全排列的基础上加了去重的判断class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] used;//元素个数确定,数组也行,不对不行,要用path.size==nums.length去判断结束,只能用Listpublic List<List<Integer>> permuteUnique(int[] nums) {//子叶上收集,判断深度方向上结束后收割used = new int[nums.length];Arrays.sort(nums);backtricking(nums,0);return result;}private void backtricking(int[] nums,int index){if(path.size() == nums.length) {result.add(new ArrayList(path));}for(int i=0;i<nums.length; i++){if(used[i] != 0 || (i>0 && nums[i] == nums[i-1] && used[i-1] == 0) ) continue;// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过// 只是全排列的基础上加了去重的判断used[i] = 1;path.add(nums[i]);index++;backtricking(nums,index);index--;path.remove(path.size() - 1);used[i]=0;}}}
感谢大佬分享:
