C++ 222ms 30lines solution without recurse, beats 100%.


  • 2
    M
    class Solution {
    public:
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> ans(0);
            if(nums.size()<2) return ans;
            int fst[nums.size()];       //first
            bool rep[nums.size()];      //repeat
            for(int i=0;i<nums.size();++i){
                fst[i]=ans.size();
                rep[i]=false;
                for(int j=i-1;j>=0;--j){
                    if(nums[j]<=nums[i]){
                        if(!rep[j]){
                            ans.emplace_back(vector<int>(2,nums[i]));
                            ans.back()[0]=nums[j];
                        }
                        for(int k=fst[j];k<fst[j+1];++k){
                            ans.push_back(ans[k]);
                            ans.back().emplace_back(nums[i]);
                        }
                        if(nums[j]==nums[i]){
                            rep[i]=true;
                            break;
                        }
                    }
                }
            }
            return ans;
        }
    };

Log in to reply
 

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