【练习】【类似于子集问题】力扣491. 非递减子序列/递增子序列-题解1（加注释）

class Solution {
private:
    vector<vector<int>> ans;  // 存储所有符合条件的子序列
    vector<int> path;         // 存储当前递归路径中的子序列

    // 回溯函数，用于生成所有非递减子序列
    void backtracking(vector<int>& nums, int start) {
        // 如果当前路径中的子序列长度大于等于 2，将其加入结果
        if (path.size() >= 2) ans.push_back(path);

        // 使用临时数组 tmp 去重，确保同一层级中不会重复选择相同的元素
        vector<int> tmp(201, 0);  // 数组大小为 201，覆盖范围 [-100, 100]

        // 遍历数组，从 start 开始
        for (int i = start; i < nums.size(); i++) {
            // 如果 path 不为空且当前元素小于 path 的最后一个元素，跳过（确保子序列非递减）
            // 或者当前元素已经在本层级使用过，跳过（去重）
            if (!path.empty() && nums[i] < path.back() || tmp[100 + nums[i]] == 1) continue;

            // 标记当前元素为已使用
            tmp[100 + nums[i]] = 1;

            // 将当前元素加入路径
            path.push_back(nums[i]);

            // 递归调用，处理下一个元素
            backtracking(nums, i + 1);

            // 回溯：移除当前元素，尝试其他可能性
            path.pop_back();
        }
    }

public:
    // 主函数，生成所有非递减子序列
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // 从索引 0 开始回溯
        backtracking(nums, 0);

        // 返回所有符合条件的子序列
        return ans;
    }
};