Evolve from intuitive solution to optimal


  • 6

    This is similar to Subsets II.

    1. O(n2^n) For each number, we can either take it or drop it. Duplicates are removed by set.
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            set<vector<int>> res;
            vector<int> one;
            find(0,nums, one, res);
            return vector<vector<int>>(res.begin(),res.end());
        }
        void find(int p, vector<int>& nums, vector<int>& one, set<vector<int>>& res) {
            if(p==nums.size()) {
                if(one.size()>1) res.insert(one);
                return;
            }
            if(one.empty()||nums[p]>=one.back()) {
                one.push_back(nums[p]);
                find(p+1,nums,one,res);
                one.pop_back();
            }
            find(p+1,nums,one,res);
        }
    
    1. We can also generate all increasing subsequences by adding each number to the current sequencies iteratively and use set to remove duplicates.
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> seq(1);
            set<vector<int>> bst;
            for(int i=0;i<nums.size();i++) {
                int n = seq.size();
                for(int j=0;j<n;j++)
                    if(seq[j].empty() || seq[j].back()<=nums[i]) {
                        seq.push_back(seq[j]);
                        seq.back().push_back(nums[i]);
                        if(seq.back().size()>1) bst.insert(seq.back());
                    }  
            }
            return vector<vector<int>>(bst.begin(),bst.end());
        }
    
    1. We can do better by not generating duplicates. When adding a duplicate number to existing sequences, we don't need to add to all sequences because that will create duplicate sequence. We only need to add to the sequences created since adding this number last time.
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> res(1);
            unordered_map<int,int> ht;
            for(int i=0;i<nums.size();i++) {
                int n = res.size();
                int start = ht[nums[i]];
                ht[nums[i]] = n;
                for(int j=start;j<n;j++)
                    if(res[j].empty() || res[j].back()<=nums[i]) {
                        res.push_back(res[j]);
                        res.back().push_back(nums[i]);
                    }  
            }
            for(int i=res.size()-1;i>=0;i--) 
                if(res[i].size()<2) {
                    swap(res[i],res.back());
                    res.pop_back();
                }
            return res;
        }
    
    1. Duplicates can also be avoided in recursion. Starting from a given number, we pick the next number. We cache the numbers already tried to avoid duplicates.
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> res;
            vector<int> one;
            find(0,nums,one,res);
            return res;
        }
        void find(int p, vector<int>& nums, vector<int>& one, vector<vector<int>>& res) {
            int n = nums.size();
            if(one.size()>1) res.push_back(one);
            unordered_set<int> ht;
            for(int i=p;i<n;i++) {
                if((!one.empty() && nums[i] < one.back()) || ht.count(nums[i])) continue;
                ht.insert(nums[i]);
                one.push_back(nums[i]);
                find(i+1,nums,one,res);
                one.pop_back();
            }
        }
    

  • 0
    R

    The 3rd solution is really excellent. Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.