Leetcode 491 Solution

This article provides solution to leetcode question 491 (increasing-subsequences).
Categories:
Tags:
Access this page by simply typing in "lcs 491" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/increasing-subsequences

Solution

class Solution {
    set<vector<int>> m_res;
public:
    void find(vector<int>& nums, int i, vector<int>& curr)
    {
        if (i == nums.size())
        {
            if (curr.size() >= 2)
                m_res.insert(curr);
            return;
        }
        
        if (curr.empty() || nums[i] >= curr.back())
        {
            curr.push_back(nums[i]);
            find(nums, i + 1, curr);
            curr.pop_back();
        }

        find(nums, i + 1, curr);
    }
    
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> curr;
        find(nums, 0, curr);
        vector<vector<int>> res;
        for (auto v : m_res)
            res.push_back(v);
        return res;
    }
};