本文主要是介绍491. 递增子序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

✅做题思路or感想

这一题依旧是子序列问题，用回溯法

然而这道题在有相同元素的情况下还要求不同的递增子序列，这就代表了不能对原数组进行排序！，因此就不能像前面一样用used数组进行树层去重了

我思来想去找不到更好的方法，只能靠用set强行去重来AC了，惭愧

class Solution {
public:
    vector<vector<int>>result;
    vector<int>temp;
    void dfs(vector<int>& nums, int startIndex) {
        for (int i = startIndex; i < nums.size(); i++) {
            //保证子序列的递增
            if (temp.size() < 1 || temp.back() <= nums[i]) {
                temp.push_back(nums[i]);
                //子序列的长度至少为2
                if (temp.size() > 1)result.push_back(temp);
                dfs(nums, i + 1);
                temp.pop_back();	//回溯
            }
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(nums, 0);
        //使用set暴力去重
        set<vector<int>>Set(result.begin(), result.end());
        return vector<vector<int>>(Set.begin(), Set.end());
    }
};

这篇关于491. 递增子序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！