491. 递增子序列 - Non-decreasing Subsequences

🎯 问题描述（来源于LeetCode）

描述：
给定一个整数数组 nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。
可以按任意顺序返回答案。
数组中的元素可能重复，但两个子序列如果元素相同（顺序相同）则视为相同子序列，因此需要去重。

说明：

子序列不要求连续，但顺序必须与原数组顺序一致。
递增子序列是严格递增的吗？题目要求「递增」通常指非递减（即允许相等），但原题描述为「递增子序列」，实际测试用例中相等的元素视为不递增（如 [4,4] 是否有效？LeetCode 491 的示例中 [4,4] 不被认为是递增子序列）。注意：题目中的「递增」通常指严格递增（nums[i] < nums[j]）。但在你的代码中使用了 nums[i] >= path[-1]，即允许相等，这可能导致不符合题目要求。需根据实际题意确认。

示例：

示例 1：

1 2	输入: nums = [4,6,7,7] 输出: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

1 2	输入: nums = [4,4,3,2,1] 输出: [[4,4]]

💻 解题思路

思路：回溯法（DFS） + 同一层去重

算法步骤

获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。
定义递归函数 dfs(start)，表示从下标 start 开始枚举下一个元素：
- 如果当前路径长度 >= 2，则将 path 的副本加入 ans（注意：继续递归，因为还可以延长）。
- 使用一个集合 used 记录在本层递归中已经尝试过的元素值，以避免重复子序列（因为相同值在同一层多次选择会产生重复结果）。
- 遍历 i 从 start 到 n-1：
  - 如果 nums[i] 已经在 used 中，则跳过（剪枝）。
  - 如果 path 为空或者 nums[i] >= path[-1]（满足非递减条件），则：
    - 将 nums[i] 加入 used。
    - 将 nums[i] 加入 path。
    - 递归调用 dfs(i+1)。
    - 回溯：path.pop()。
从 dfs(0) 开始搜索。
返回 ans。

代码实现

from typing import List

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []

        def dfs(start):
            if len(path) >= 2:
                ans.append(path[:])
            used = set()
            for i in range(start, n):
                if nums[i] in used:
                    continue
                if not path or nums[i] >= path[-1]:
                    used.add(nums[i])
                    path.append(nums[i])
                    dfs(i + 1)
                    path.pop()

        dfs(0)
        return ans

📊 性能分析

时间复杂度： $O(2^n)$ ，每个元素可以选择或不选择，但通过剪枝和去重，实际运行较快。对于 n ≤ 15 通常可接受。
空间复杂度： $O(n \cdot 2^n)$ ，存储所有结果，加上递归栈深度 $O(n)$ 。

思考

该解法通过回溯枚举所有可能的递增子序列，并利用 used 集合在同一层去重，保证相同值不会在同一递归层被重复选取，从而避免重复子序列。
优点：

逻辑清晰，直接模拟了子序列的构建过程。
去重策略高效，避免了最终对结果集进行重复判断。

注意事项：

条件 nums[i] >= path[-1] 允许相等，即非递减。但 LeetCode 491 原题要求的是严格递增（如 [4,4] 不是有效子序列）。若需要严格递增，应将条件改为 nums[i] > path[-1]。请根据题目要求调整。
由于题目允许返回任意顺序，结果顺序无关紧要。
该方法不会遗漏任何子序列，因为每个子序列都对应唯一的一种选择路径（按原顺序选取）。

改进建议：