【代码随想录day 25】 力扣 491. 递增子序列

视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html#%E6%80%9D%E8%B7%AF
力扣题目：https://leetcode.cn/problems/non-decreasing-subsequences/

这道题和前面几道题有相似之处，但是仍有一些不一样的地方

1. 输入的数组不能排序，比如4767和4677输出的结果就不一样
2. 不能排序还要递增序列就意味着需要比较大小来判断下一位该不该要，如果下一位小于上一次存入的数据，记住是存入path的数据，因为输入数组的无序性和不可更改性导致需要和存入的数据来判断，所以每次判断一下nums[i] 和path.back()的大小关系，如果nums[i]小于path.back()，直接continue。
3. 不能排序还带来一个问题就是我们去重时不能比较used[i-1] == ture了，因为重复的地方可能不连贯，所以我们在这里采用unordered_set这一数据结构，每一层的数据都会存入set中，如果发现有重复元素存在，直接continue

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    
    void backtracking(vector<int> &nums, int startIndex)
    {
        //存path
        if(path.size() > 1)
        {
            result.push_back(path);
        }
        //判断终止条件
        if(startIndex > nums.size())
        {
            return;
        }
        //定义set
        unordered_set<int> uset;
        //单层搜索
        for(int i = startIndex; i < nums.size(); i++)
        {
            //剪枝
            /*
            如果下一个元素小于path的最后一个元素返回
            或者当前遍历元素之前有出现过
            直接跳
            */
            if(!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end())
            {
                continue;
            }
            //存入path元素
            path.push_back(nums[i]);
            //存入set中
            uset.insert(nums[i]);
            //回溯
            backtracking(nums, i+1);
            path.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        int last = nums[0];
        path.clear();
        result.clear();

        backtracking(nums, 0);
        return result;
    }
};