491.Increasing Subsequences

Description

Solution

Two solutions:

• DP, use set<vector<int>> to deduplicate
• Back Tracking, don’t forget deduplicating

Code

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<vector<int>>> dp(nums.size());
        set<vector<int>> Set;
        for(int i = 0; i < nums.size(); i ++){
            dp[i].push_back({nums[i]});
            for(int j = 0; j < i; j++){
                if(nums[i] >= nums[j]){
                    for(auto sequence: dp[j]){
                        //sequence -> vector<int>
                        dp[i].push_back(sequence);
                        dp[i].back().push_back(nums[i]);
                        Set.insert(dp[i].back());
                    }
                }
            }
        }
        vector<vector<int>> res;
        for(auto seq : Set){
            res.push_back(seq);
        }
        return res;
    }
};

Solution2 :

class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> curRes;
        backtrack(nums, 0, curRes);
        return res;
    };

    void backtrack(vector<int>& nums, int curPos, vector<int>& curres){
        if(curres.size() > 1)
            res.push_back(curres);
        if(curPos == nums.size())
            return;
        unordered_set<int> seen;
        for(int i = curPos; i < nums.size(); i++){
            if(curres.size()>0 && nums[i] < curres.back())
                continue;
            if(seen.count(nums[i]))
                continue;
            curres.push_back(nums[i]);
            backtrack(nums, i+1, curres);
            curres.pop_back();
            seen.insert(nums[i]);
        }
    }
};