LeetCode 491. 非递减子序列

2023-08-18 HGNULB 约 9 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 491. 非递减子序列

题意分析

要求找出数组中所有元素个数至少为 2 的非递减子序列，答案里不能出现内容重复的两个子序列，但顺序不限。子序列意味着元素在原数组中的相对次序必须保持，可以跳过任意个元素但不能重排。

「非递减」允许相等，所以 [7, 7] 是合法的；「至少两个元素」把单元素和空序列排除在外。这两条决定了收集答案的时机。

最关键的隐含约束是：原数组本身没有排序，而且不能排序——一旦排序，元素的相对次序就被破坏，产生的子序列不再是原数组的子序列。这一点把本题和常见的组合去重题彻底区分开。

数组长度上限只有 15，取值范围是 -100 到 100。长度 15 说明答案总量最多是 $2^{15}$ 量级，穷举所有子序列是可行的；取值范围很窄则暗示重复元素普遍存在，去重是必须认真处理的部分。

边界包括：全部元素相同时答案是所有长度不小于 2 的连续截取形式，各自只应出现一次；严格递减的数组没有任何合法子序列，返回空列表。

解法：回溯 + 去重

核心思路

既然长度只有 15，思路的起点就是枚举每个元素「选或不选」，共 $2^{15}$ 种组合，逐一检查是否非递减且长度不小于 2。这样能拿到正确答案，但两个问题：一是大量组合在很早就已经违反非递减，检查到最后才丢弃是浪费；二是重复元素会让同一个内容被生成多次。

第一个问题的解法是把「先生成后检查」改成「边生成边剪枝」：在往路径里添加元素时就要求它不小于路径末尾，一旦不满足直接跳过这个候选。这样搜索树上活着的每一条路径都天然是一个合法的非递减序列，不需要事后验证。于是可以在进入每个递归节点时立刻收集答案——只要路径长度达到 2 就存一份拷贝，而且不需要写终止条件，下标越界时循环自然不执行。

第二个问题要先想清楚重复是怎么产生的。以 [4, 7, 7] 为例，路径 [4, 7] 可以由选下标 1 得到，也可以由选下标 2 得到，两者内容完全一样。抽象地说，同一个递归层里，如果在同一个位置放入了两个数值相同的元素，那么它们各自展开的整棵子树都是完全重复的。

由此得到去重的不变量：在每一个递归层内，同一个数值只允许被选作该位置的元素一次。实现上给每层准备一个局部的已用值集合，选之前先查、选之后记入。注意这个集合必须是「每层一个」而不是「全局一个」——全局集合会误杀掉不同层里合法复用同一数值的情况，比如 [7, 7] 中第二个 7 出现在下一层，是必须保留的。

这里也解释了为什么本题不能用「排序后判断 nums[i] == nums[i-1] 就跳过」这个常见去重套路：那个套路依赖数组有序，而本题恰恰不能排序。局部集合是不依赖有序性的通用替代。

解题步骤

准备结果列表和当前路径，从下标 0 进入递归。路径用可变列表维护，进出各一次，避免每层复制带来的额外开销。

进入递归后先做收集：路径长度不小于 2 就把它的一份拷贝加入结果。必须是拷贝，因为路径本身后续还会被修改。收集写在函数开头而不是循环里，是因为搜索树上每个节点都对应一个完整的候选答案。

在当前层创建一个空的已用值集合。它的生命周期严格等于这一层的循环，递归返回后随栈帧销毁，这正是「层内去重、层间不干扰」所需要的语义。

从 start 枚举到数组末尾。两个跳过条件：路径非空且候选值小于路径末尾（破坏非递减），或候选值在本层已经用过（会产生重复子树）。两个条件相互独立，顺序无所谓。

通过检查后把候选值加入路径，递归到 i + 1。传 i + 1 而不是 start + 1，保证了每个元素最多被用一次，且下标严格递增，这正是子序列的定义。

递归返回后从路径尾部弹出刚加入的元素，恢复现场。已用值集合不需要恢复——它记录的是「这一层已经试过的数值」，本来就应该在整个循环期间持续累积。

以 nums = [4, 6, 7, 7] 走一遍：进入 dfs(0)，路径为空，本层集合为空。

选下标 0 的 4，路径变成 [4]，集合记下 4，进入 dfs(1)。路径长度 1 不收集，新建空集合。选下标 1 的 6（不小于 4），路径 [4, 6]，进入 dfs(2)：长度达到 2，收集 [4, 6]。继续选下标 2 的 7，路径 [4, 6, 7]，进入 dfs(3) 收集 [4, 6, 7]；再选下标 3 的 7（等于 7，非递减成立），路径 [4, 6, 7, 7]，进入 dfs(4) 收集 [4, 6, 7, 7]，循环不执行，逐层回退。回到 dfs(3) 那一层时循环已走完；回到 dfs(2) 的循环，下标 3 的 7 与本层已用的 7 相同，跳过——这一步避免了再生成一遍 [4, 6, 7]。

回到 dfs(1)，弹出 6，本层集合已含 6。选下标 2 的 7，路径 [4, 7]，进入 dfs(3) 收集 [4, 7]，再选下标 3 的 7 得到 [4, 7, 7] 并收集。回退后 dfs(1) 的循环走到下标 3，其值 7 已在本层集合中，跳过。

回到 dfs(0)，弹出 4，本层集合含 4。选下标 1 的 6，路径 [6]，展开后依次收集 [6, 7] 和 [6, 7, 7]。再选下标 2 的 7，路径 [7]，展开收集 [7, 7]。最后走到下标 3，其值 7 已在顶层集合中，跳过——正是这一跳避免了重复产出 [7, 7]。

最终结果依次是 [4,6]、[4,6,7]、[4,6,7,7]、[4,7]、[4,7,7]、[6,7]、[6,7,7]、[7,7]，共八个，与题目样例一致。

代码实现

class Solution {
    // 回溯路径必须保持非递减，候选值小于路径末尾时直接跳过。
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }
        Set<Integer> used = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            if (!used.add(nums[i])) {
                continue;
            }

            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func findSubsequences(nums []int) [][]int {
    // 回溯路径必须保持非递减，候选值小于路径末尾时直接跳过。
    res := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(start int)
    dfs = func(start int) {
        if len(path) >= 2 {
            pathCopy := make([]int, len(path))
            copy(pathCopy, path)
            res = append(res, pathCopy)
        }
        used := make(map[int]struct{})
        for i := start; i < len(nums); i++ {
            if len(path) > 0 && nums[i] < path[len(path)-1] {
                continue
            }
            if _, ok := used[nums[i]]; ok {
                continue
            }
            used[nums[i]] = struct{}{}

            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return res
}

复杂度分析

时间复杂度：$O(n \cdot 2^n)$，搜索树的节点数上界是全部 $2^n$ 个子序列，每命中一个合法答案还要花 $O(n)$ 拷贝路径。非递减剪枝和层内去重只会让实际访问的节点更少，不改变上界。

空间复杂度：$O(n)$（不计结果列表），递归深度不超过 $n$，路径长度不超过 $n$，每层的已用值集合大小也不超过该层剩余元素个数，栈上所有集合的总规模仍是线性的。

关键点总结

约束能剪枝就不要留到事后校验。把「非递减」作为选取候选的前置条件，搜索树上每个节点就都是合法答案，收集逻辑随之简化成一句话。

搜索树中每个节点都是答案时，收集动作应写在递归入口而非叶子处，也不需要显式的终止条件——循环范围为空时递归自然结束。

去重的正确抽象是「同一层的同一个位置不重复放同一数值」，而不是「同一个数值只用一次」。区分这两者是本题与全排列、组合类去重题共通的核心。

常见的「排序后跳过相邻相同元素」套路依赖有序性，凡是要求保持原序的题目都用不了，必须换成每层一个局部集合。

已用值集合不参与回溯撤销，它的作用域天然由栈帧界定；反过来，路径必须撤销。搞混这两者的生命周期是最典型的错误来源。

面试视角：先说清「重复从哪来」再动手写去重，比直接甩出一个集合更有说服力。面试官常追问「为什么不能先排序去重」，答案就是排序破坏子序列定义；再追问优化，可以提到取值范围只有 -100 到 100，每层的集合可以换成长度 201 的布尔数组，常数更小。

易错点总结

错误写法：先排序再用「跳过相邻相同元素」的经典去重。nums = [4, 3, 5] → 排序后得到 [3, 4, 5]，会输出 [3, 4]、[3, 5] 等根本不是原数组子序列的结果，正确答案只有 [4, 5] 和 [3, 5]。

错误写法：把已用值集合提到递归函数外面当全局变量。nums = [7, 7] → 第二个 7 在下一层被误判为「已用过」，[7, 7] 丢失，输出空列表。

错误写法：在递归返回后把当前值从已用值集合中删除。nums = [4, 7, 7] → 本层第二个 7 不再被跳过，[4, 7] 被产出两次。

错误写法：只在路径为空时才允许任意取值，却忘了比较非空路径的末尾元素。nums = [4, 3] → 会输出 [4, 3]，而它并非非递减序列，正确答案是空列表。

错误写法：把非递减条件写成严格递增。nums = [7, 7] → [7, 7] 被判为不合法，输出空列表，正确答案含 [7, 7]。

错误写法：递归时传 start + 1 而不是 i + 1。nums = [4, 6, 7] → 下标不再严格递增，同一个元素可能被跳过或被重复使用，产出 [4, 4] 这类非法结果。

错误写法：收集答案时直接把路径引用存进结果列表。任意有解用例 → 回溯弹出元素后结果里的所有条目跟着一起变短，最终全部退化成空列表或相同内容。

错误写法：把收集条件写成路径长度大于等于 1，或写在循环内部而不是递归入口。nums = [4, 6] → 前者会额外输出 [4]、[6] 这些长度为 1 的序列，后者会漏掉最深处那一层的路径。

错误写法：加一个「路径长度等于数组长度就返回」的终止条件却忘了先收集。nums = [7, 7] → 最长的那个答案在收集前就被提前返回掉了。

相似题目

题目	难度	考察点
78. 子集	中等	无重复元素的子集枚举，是本题去掉两个约束后的骨架
90. 子集 II	中等	允许排序，可用相邻相同跳过法，正好与本题形成对照
47. 全排列 II	中等	去重同样发生在层内，但还要额外维护全局使用标记
46. 全排列	中等	每层都从头枚举，靠使用标记而非起始下标控制取值范围
39. 组合总和	中等	元素可重复选取，递归时传 `i` 而不是 `i + 1`
40. 组合总和 II	中等	目标和作为剪枝依据，排序后可提前终止整层循环
300. 最长递增子序列	中等	同样的递增子序列结构，但只要长度，用动态规划而非枚举