# Multiple approaches topdown, bottom up, recursive

• 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;

}

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