代码随想录算法训练营第二十九天 |491.递增子序列，46.全排列，47.全排列II（待补充）

╰+攻爆jí腚メ 2024-04-23 04:14 75阅读 0赞

### 491.递增子序列 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

*  输入: \[4, 6, 7, 7\]
 *  输出: \[\[4, 6\], \[4, 7\], \[4, 6, 7\], \[4, 6, 7, 7\], \[6, 7\], \[6, 7, 7\], \[7,7\], \[4,7,7\]\]

说明:

*  给定数组的长度不会超过15。
 *  数组中的整数范围是 \[-100,100\]。
 *  给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

4、视频链接：

[回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列\_哔哩哔哩\_bilibili][_ LeetCode_491._bilibili]

5、思路：

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集，又是去重，是不是不由自主的想起了刚刚讲过的[90.子集II(opens new window)][90._II_opens new window]。

就是因为太像了，更要注意差别所在，要不就掉坑里了！

在[90.子集II(opens new window)][90._II_opens new window]中我们是通过排序，再加一个标记数组来达到去重的目的。

而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

**所以不能使用之前的去重逻辑！**

本题给出的示例，还是一个有序数组 \[4, 6, 7, 7\]，这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比，我用\[4, 7, 6, 7\]这个数组来举例，抽象为树形结构如图：

![83ec61a9899fc25068c9462e620b2475.png][]

class Solution {
        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) {
            // 递增子序列的长度至少是2
            if (path.size() >= 2) {
                result.add(new ArrayList<>(path));
                // 注意这里不要加return，因为要取树上的所有节点
            }
            // 定义一个hashset来剪枝
            HashSet<Integer> hs = new HashSet<>();
            for (int i = startIndex; i < nums.length; i++) {
                // 剪枝
                // 1. path里已经包含的元素
                // 2. 当前元素比path里最后一个元素还小
                // 3. 当前元素已经在hs里了
                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.removeLast();
            }
        }
    }

### 46.全排列 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

*  输入: \[1,2,3\]
 *  输出: \[ \[1,2,3\], \[1,3,2\], \[2,1,3\], \[2,3,1\], \[3,1,2\], \[3,2,1\] \]

4、视频链接：

[回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集\_哔哩哔哩\_bilibili][_ LeetCode_78._bilibili]

5、**首先排列是有序的，也就是说 \[1,2\] 和 \[2,1\] 是两个集合，这和之前分析的子集以及组合所不同的地方**。

可以看出元素1在\[1,2\]中已经使用过了，但是在\[2,1\]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

class Solution {
        List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
        LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    
        public List<List<Integer>> subsets(int[] nums) {
            subsetsHelper(nums, 0);
            return result;
        }
    
        private void subsetsHelper(int[] nums, int startIndex) {
            result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
            if (startIndex >= nums.length) { // 终止条件可不加
                return;
            }
            for (int i = startIndex; i < nums.length; i++) {
                path.add(nums[i]);
                subsetsHelper(nums, i + 1);
                path.removeLast();
            }
        }
    }

### 47.全排列II ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

给定一个可包含重复数字的序列 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\]\]

提示：

*  1 <= nums.length <= 8
 *  \-10 <= nums\[i\] <= 10

4、视频链接：

[回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II\_哔哩哔哩\_bilibili][LeetCode_47._ II_bilibili]

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.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;// 回溯
                }
            }
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/non-decreasing-subsequences/
[Link 1]: https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_491._bilibili]: https://www.bilibili.com/video/BV1EG4y1h78v/
[90._II_opens new window]: https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
[83ec61a9899fc25068c9462e620b2475.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/dbd3acccff62411f8a8ba128803ca164.png
[LeetCode_ - 1]: https://leetcode.cn/problems/permutations/
[Link 2]: https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_78._bilibili]: https://www.bilibili.com/video/BV1U84y1q7Ci
[LeetCode_ - 2]: https://leetcode.cn/problems/permutations-ii/
[Link 3]: https://www.programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
[LeetCode_47._ II_bilibili]: https://www.bilibili.com/video/BV1R84y1i7Tm/