C++ Solution using STL


  • 0

    class Solution {
    public:

    //customized hash function to store vector<int> in unordered_Set
    struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
    

    };
    vector<vector<int> > ans;
    unordered_set<vector<int>,VectorHash > uset;

    void recur(vector<int> &nums,int index,vector<int> sol)
    {
        if(sol.size() > 1)
        {
                if(uset.find(sol) == uset.end())
                {
                    ans.push_back(sol);
                    uset.insert(sol);
                }
        }
        if(index == nums.size())
            return;
        for(int i=index;i<nums.size();i++)
        {
            if(sol.size() == 0 || nums[i] >= sol.back())
            {
                sol.push_back(nums[i]);
                recur(nums,i+1,sol);
                sol.pop_back();
            }
            else
                recur(nums,i+1,sol);
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        ans.clear();
        vector<int> sol;
        recur(nums,0,sol);
        return ans;
      
    }
    

    };


  • 0

    @harbeersamra Actually, I thought about using customized vector hasher so that I could deal with duplicates issue. However, the hash function is O(v.size()), so I also not sure about the performance.


  • 0

    @zzg_zzm still better then using find() before inserting elements in vector<vector<int> >


  • 0

    @harbeersamra said in C++ Solution using STL:

    @zzg_zzm still better then using find() before inserting elements in vector<vector<int> >

    I mean the invoke of unordered_set::find in if(uset.find(sol) == uset.end()) for hash set. If the hasher is O(N) instead of O(1), wouldn't it also impact the look-up for an element? After all, I think it is impossible to compare two vectors in O(1) time since the amount of data is O(N).


  • 0

    @zzg_zzm If I was to use find() on vector<vector<int> > , worst case complexity will be O(n^2).
    But find() on set or unordered_set is O(n) operation.


Log in to reply
 

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