Non Decreasing Subsequences

491. 非递减子序列

分析

path 数组记录当前构建中的子序列
每当 path 长度大于等于 2，就加入答案集
每次从下标 u 开始向后枚举所有可能的数字：
- 若当前数字 nums[i] 可以接在 path 的末尾（即递增），就加入递归
- 用一个哈希集合 S 记录当前层用过的数字，避免同一层出现重复元素（防止结果中出现重复子序列）

时间复杂度

时间复杂度 O(2^n)

空间复杂度

空间复杂度 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution
{
public:
    std::vector<std::vector<int>> res; // 存储所有结果
    std::vector<int> path;             // 当前构建中的子序列

    void dfs(std::vector<int>& nums, int u)
    {
        // 如果子序列长度 >= 2，就加入结果集
        if (path.size() >= 2)
            res.push_back(path);

        if (u == nums.size()) return;

        std::unordered_set<int> S; // 当前层去重

        for (int i = u; i < nums.size(); ++ i)
        {
            // 满足递增条件且未在本层用过
            if ((path.empty() || path.back() <= nums[i]) && !S.count(nums[i]))
            {
                S.insert(nums[i]);      // 标记本层已使用
                path.push_back(nums[i]);
                dfs(nums, i + 1);       // 递归下一个位置
                path.pop_back();        // 回溯
            }
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums)
    {
        dfs(nums, 0);
        return res;
    }
};