LeetCode 491. 非递减子序列

约 4 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 京东 快手
标签
数组 哈希表 位运算 回溯

题目描述

✅ 491. 非递减子序列

image-20260928224237094

题意分析

选择下标递增的一组元素，使数值非递减且长度至少为 $2$，返回所有不同的数值序列。子序列需要保持原数组中的先后顺序；重复值可以同时选择，但不同下标产生的相同结果只保留一次。

解法：回溯 + 去重

核心思路

[!blue]

回溯状态由已选序列 path 和下一次可选的起始下标 start 组成。枚举 i >= start，只有 path 为空或 nums[i] 不小于路径末尾时才选择它，再从 i + 1 继续。这样下标严格递增、数值非递减两个条件始终成立。

同一层递归对应一个固定前缀，这一层若多次选择相同数值，就会重复搜索相同前缀的结果。用本层独立的 used 集合记录已经尝试的数值，只保留最早出现的那一次：较早位置之后的可选范围更大，较晚位置能接出的任何后缀，也都能接在较早位置之后，因此不会漏解。

used 只限制同一前缀下的下一项；进入下一层要重新建集合，允许另一个相同值成为后续元素。递归返回时撤销 path 的最后一项，但保留本层 used，因为这个数值对应的分支已经完整搜索过。

每当路径长度至少为 $2$，就复制一份加入答案，并继续向下寻找更长的序列。所有合法序列都对应一组递增下标，而同层去重只删除可由更早位置覆盖的分支，所以最终结果既完整又不重复。

解题步骤

  1. 从空路径和 start = 0 开始搜索。
  2. 当前路径长度至少为 $2$ 时，复制并加入结果，随后继续搜索。
  3. 为本次调用创建 used，枚举剩余下标，跳过会造成下降或本层已经使用过的值。
  4. 记录本层已试值，向路径加入当前元素，再递归搜索它后面的部分。
  5. 返回后移除路径末尾元素，继续本层枚举。没有剩余下标时自然结束；输入不足两个元素时结果为空。

代码实现

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(n2^n)$，枚举子序列并复制输出路径。
  • 空间复杂度：不计输出为 $O(n)$。递归深度与路径长度至多为 $n$；题目值域为 $[-100,100]$，每层集合最多记录 $201$ 个值。输出最坏需要 $O(n2^n)$ 空间。

关键点总结

[!green]

  • 路径需要回溯撤销，本层已试集合不撤销。
  • 相等元素可以出现在不同深度，只要它们来自递增的下标。

易错点总结

[!yellow]

  • 排序会生成原数组中不存在的子序列。
  • 用全局集合会禁止合法重复值。
  • 直接保存路径引用，后续回溯会改变已经收集的结果。

相似题目

题目 难度 关联与区别
90. 子集 II 中等 同样对重复值做同层去重，本题必须保留原下标顺序，不能先排序输入。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/14945738
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！