0491. Non-decreasing Subsequences ================================ 题目信息 -------- :题号: 0491 :难度: Medium :主题: 子序列、非递减、长度至少二、结果去重 :原题: `LeetCode 0491 `_ :重点: 保持原下标顺序但可跳过元素、后项可等于前项、相同数值序列只返回一次、结果顺序不限 题目重述 -------- 给定整数数组 ``nums``,返回其中所有不同的非递减子序列。每个子序列长度至少为 2,并且相邻所选元素满足后一个值大于或等于前一个值。 子序列可以跳过原数组中的元素,但保留元素的下标顺序不能改变。由不同下标选择产生相同数值序列时,结果中只能保留一个副本。``nums.length`` 位于 ``[1, 15]``,每个元素位于 ``[-100, 100]``,结果顺序不限。 自建示例 -------- 重复值会产生重复下标选择: .. code-block:: text 输入:nums = [1,2,1,2] 输出可包含:[[1,1], [1,2], [2,2], [1,1,2], [1,2,2]] 解释:[1,2] 可以由多个不同下标组合得到,但作为数值序列只能返回一次;列出的五种是全部不同合法结果,顺序不限。 只有一条合法子序列: .. code-block:: text 输入:nums = [3,3,2] 输出:[[3,3]] 解释:前两个 3 构成非递减子序列,任何包含末尾 2 的长度至少为 2 的子序列都会下降。 按递归层去重并保持下标递增 -------------------------- 回溯参数 ``start`` 表示下一次只能从哪个下标之后选择,因而自动保证子序列顺序。若候选值不小于路径末尾,就可以加入路径;路径长度达到 2 时记录一份结果,然后继续向后扩展。 同一递归层中,数值相同的候选会产生相同的后续数值序列,只保留第一次尝试。这个集合必须在每层递归重新建立:同一个值在不同深度仍可能形成合法的不同长度序列。 C++ 实现 -------- .. code-block:: cpp class Solution { std::vector path; std::vector> result; void search(const std::vector& nums, int start) { if (path.size() >= 2) result.push_back(path); std::unordered_set used; for (int i = start; i < static_cast(nums.size()); ++i) { if (used.count(nums[i])) continue; used.insert(nums[i]); if (!path.empty() && nums[i] < path.back()) continue; path.push_back(nums[i]); search(nums, i + 1); path.pop_back(); } } public: std::vector> findSubsequences( std::vector& nums) { path.clear(); result.clear(); search(nums, 0); return result; } }; 代码分析 -------- ``start`` 只向右移动,保证每条路径是原数组的子序列;层内去重只删除相同值、相同前缀下的重复分支,不会删除跨层的合法序列。最坏时间复杂度与不同子序列数量同阶,额外空间为 ``O(n)`` 的递归路径和去重集合(不计输出)。