491.递增子序列
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！Github：https://github.com/youngyangyang04/leetcode-master, 视频播放量 39561、弹幕量 841、点赞数 1414、投硬币枚数 1587、收藏人数 195、转发人数 46, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：带你学透回溯算法（理论篇）| 回溯法精讲！，回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II，这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II，回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独，带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！，带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！，动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列，组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列
https://www.bilibili.com/video/BV1EG4y1h78v/
思考：不能排序，重点在去重，在每层用个map来标记被该元素是否被使用过。使用过就跳过来达到去重的目的。
class Solution {public static List<List<Integer>> result = new ArrayList<>();public static List<Integer> path = new ArrayList<>();public static List<List<Integer>> findSubsequences(int[] nums) {HashSet<Integer> used = new HashSet<>();result.clear();backtracking(nums, 0);return result;}public static void backtracking(int[] nums, int startIndex) {if (path.size() >= 2) {result.add(new ArrayList<>(path));}if (startIndex >= nums.length) {return;}HashSet<Integer> used = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if (used.contains(nums[i])) {continue;}if (path.size() > 0 && nums[i] < path.get(path.size() - 1)) {continue;}used.add(nums[i]);path.add(nums[i]);backtracking(nums, i + 1);path.remove(path.size() - 1);}}
}46.全排列
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.comGithub：https://github.com/youngyangyang04/leetcode-master, 视频播放量 56084、弹幕量 447、点赞数 1168、投硬币枚数 850、收藏人数 344、转发人数 84, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：当你过度准备了一场代码面试时……，震惊！汤家凤老师曾经是个程序员？？？自称编程水平一流！冒泡排序讲得头头是道！，【neko算法课】N皇后问题 回溯法【13期】，国内算法大佬左程云VS清华大佬马士兵：Leetcode刷题200道，足以吊打字节面试官！，回溯算法套路③排列型回溯+N皇后【基础算法精讲 16】，小学生也能学会的【排列组合】，5分钟理解回溯算法，如何理解排列组合？，46. 全排列 Permutations 【LeetCode 力扣官方题解】，全排列问题https://www.bilibili.com/video/BV19v4y1S79W/
思考：与组合不同之处在与每次递归startIndex从0开始。
class Solution {public static List<List<Integer>> result = new ArrayList<>();public static List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {result.clear();boolean[] used = new boolean[nums.length];backtracking(nums, used);return result;}public static 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] == false) {path.add(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.remove(path.size()-1);} else {continue;}}}
}47.全排列 II
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.comGithub：https://github.com/youngyangyang04/leetcode-master, 视频播放量 40361、弹幕量 494、点赞数 944、投硬币枚数 761、收藏人数 194、转发人数 35, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：震惊！汤家凤老师曾经是个程序员？？？自称编程水平一流！冒泡排序讲得头头是道！，当你过度准备了一场代码面试时……，我更完了，你看完了吗？，【neko算法课】N皇后问题 回溯法【13期】，贪心算法理论基础！，贪心算法，合并区间有细节！LeetCode：56.合并区间，回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列，关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序，贪心算法，怎么跳跃不重要，关键在覆盖范围 | LeetCode：55.跳跃游戏，chapt5-2-回溯-全排列https://www.bilibili.com/video/BV1R84y1i7Tm/
思考：去重用used数组来区分是树枝还是树层。
class Solution {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.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++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == false) {used[i] = true;path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);used[i] = false;}}}
}
