非递减子序列(attention)

题目

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

思路

依然是回溯的模板，但是每次递归的判断需要改变

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void findSubsequencesAux(vector<int>& nums, int start_index)
    {
        for(int i = start_index; i < nums.size(); ++i)
        {
            if(i > start_index && nums[i] == nums[i-1]) continue;
            if(!path.empty())
            {
                if(nums[i] >= path[path.size() - 1])
                {
                    path.emplace_back(nums[i]);
                    res.emplace_back(path);
                }
                else
                {
                    continue;
                }
            }
            else
            {
                if(find(nums.begin(), nums.begin() + i, nums[i]) != nums.begin() + i) continue;
                if(i == nums.size() - 1) continue;
                path.emplace_back(nums[i]);
            }
            findSubsequencesAux(nums, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        findSubsequencesAux(nums, 0);
        return res;
    }
};

做了半个多小时，通过了40多个案例，改了一个小时，通过了51个案例。为了满足不同的案例，一直在原代码上增加条件约束，导致多了很多条件约束，并且没有满足所有的案例，可能在添加约束的过程中就已经相互冲突了；这时，应该重新审视这道题目。

看了代码随想录

这个和之前有序数组的去重是不一样的，有序数组的元素相同的元素必然是相近的，但是这个题目的数组并不能排序，所以不能直接使用if(i > start_index && nums[i] == nums[i-1]) continue;来筛选相同的元素，需要在每次设置一个set来记录使用过的元素

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void findSubsequencesAux(vector<int>& nums, int start_index)
    {
        unordered_set<int> use_elem_set;
        for(int i = start_index; i < nums.size(); ++i)
        {
            if(find(use_elem_set.begin(), use_elem_set.end(), nums[i]) != use_elem_set.end()) continue;
            if(path.empty() || (!path.empty() && nums[i] >= path[path.size() - 1]))
            {
                path.emplace_back(nums[i]);
                use_elem_set.insert(nums[i]);
                if(path.size() >= 2)  res.emplace_back(path); 
            }
            else  continue;
            findSubsequencesAux(nums, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        findSubsequencesAux(nums, 0);
        return res;
    }
};

改变开始的判断，再次画图推理