非递减子序列习题分析

习题：（leetcode491）

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

分析：

此题要在数组中找出所有的不同递增子序列，我们可以使用回溯进行求解。

对于去重操作是此题的重点。对于求递增子序列，原数组的元素顺序就不能改变，这就不能使用sort进行遍历数组来进行比较去重，所以我们可以介入set或map来进行去重操作。

在使用set或map去重时要注意不可直接作为类成员，要放在每次回溯中。

代码分析：

class Solution {
private:
    vector<vector<int>> result; // 存储所有符合条件的子序列
    vector<int> path; // 存储当前找到的子序列
    // 回溯函数
    void backtracking(std::vector<int>& nums, int startIndex) {
        // 如果当前路径长度大于1，则将其添加到结果中
        if (path.size() > 1) {
            result.push_back(path);
        }
        // 使用数组去重，由于数值范围是[-100, 100]，因此偏移100使其变为非负
        int used[201] = {0}; 

        // 从startIndex开始遍历数组
        for (int i = startIndex; i < nums.size(); i++) {
            // 如果当前数字小于路径中的最后一个数字，或者本层已经使用过这个数字，则跳过
            if ((!path.empty() && nums[i] < path.back())
                || used[nums[i] + 100] == 1) {
                continue;
            }
            // 标记当前数字为已使用
            used[nums[i] + 100] = 1;
            // 将当前数字添加到路径中
            path.push_back(nums[i]);
            // 递归调用回溯函数，从下一个索引开始
            backtracking(nums, i + 1);
            // 回溯，移除路径中的最后一个数字
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear(); // 清空结果
        path.clear(); // 清空路径
        backtracking(nums, 0); // 从索引0开始回溯
        return result; // 返回结果
    }
};