LeetCode第491題:増分サブシーケンス(C++)

491.増分サブシーケンス-力ボタン(LeetCode)
すべてが見つかります...
この問題は簡単そうに見えますが、重くするのは本当に頭が痛いです.遡及法の列挙でいいと思っていたが、繰り返される例がある.
最後に参考にしました:491.増分サブシーケンス:【深さ検索&遡及】詳細-増分サブシーケンス-力ボタン(LeetCode)

class Solution {
public:
    vector> res;
    void backtrack(vector &nums, vector &tmp, int idx){
        if(tmp.size() > 1)  res.push_back(tmp);
        unordered_set s;
        for(int i = idx; i < nums.size(); ++i){
            if((tmp.empty() || tmp.back() <= nums[i]) && s.count(nums[i]) == 0){
                tmp.push_back(nums[i]);
                backtrack(nums, tmp, i+1);
                tmp.pop_back();
                s.insert(nums[i]); //     ，         ，       
            }
        }
    }
   
    vector> findSubsequences(vector& nums) {
        vector tmp;
        backtrack(nums, tmp, 0);
        return res;
    }
};

配列の使用

class Solution {
public:
    vector> res;
    void backtrack(vector &nums, vector &tmp, int idx){
        if(tmp.size() > 1)  res.push_back(tmp);
        int hash[201] = {0}; //              ，       [-100, 100]
        for(int i = idx; i < nums.size(); ++i){
            if((tmp.empty() || tmp.back() <= nums[i]) && hash[nums[i] + 100] == 0){
                tmp.push_back(nums[i]);
                backtrack(nums, tmp, i+1);
                tmp.pop_back();
                hash[nums[i]+100] = 1;
            }
        }
    }
   
    vector> findSubsequences(vector& nums) {
        vector tmp;
        backtrack(nums, tmp, 0);
        return res;
    }
};