Multiple approaches topdown, bottom up, recursive


  • 3
    L

    Build up, DP table

    vector<int> grayCode_dp(int n) {
        if( n == 0) return {0};
        vector<int> prev={0};
        
        for( int cur=1; cur<=n; cur++)
            for( int j=prev.size()-1; j>=0; j--)
                    prev.push_back( (1<<(cur-1))|prev[j]);    
        return prev;
    }
    

    top down, Just recursive

    vector<int> grayCode_rec(int n) {
        
        if( n == 0) return {0};
        if( n == 1) return {0,1};
        
        vector<int> cur;
        vector<int> prev=grayCode(n-1);
        for( auto val : prev )
        {
            cur.push_back( (0<<n)|val);    
        }
        for( int j=prev.size()-1;j>=0;j--)
        {
            cur.push_back( (1<<(n-1))|prev[j]);    
        }
        return cur;
    }
    

    };

    Truncated BFS with O(1 shft by n) space

        vector<int> res;
    void gc(int n, int cur, vector<bool> &exists )
    {
        
        
        for(int i=0;i<n;i++)
        {
            int temp= cur^ (1<<i);
            
            if(exists[temp] == false)
            {
                exists[temp]=true;
                res.push_back(temp);
                gc(n, temp, exists);
                break;
            }
        }
        
    }
    vector<int> grayCode(int n , int cur=0) {
        
        
        vector<bool> exists(1<<n,false);
        exists[0]=true;
        res.push_back(0);
        gc(n,0, exists);
        
        return res;
        
        
    }

Log in to reply
 

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