A backtracking approach to generate n bit Gray Codes | CPP program to find the gray sequence of n bits . ; we have 2 choices for each of the n bits either we can include i . e invert the bit or we can exclude the bit i . e we can leave the number as it is . ; base case when we run out bits to process we simply include it in gray code sequence . ; ignore the bit . ; invert the bit . ; returns the vector containing the gray code sequence of n bits . ; num is passed by reference to keep track of current code . ; Driver function .
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; void grayCodeUtil ( vector < int > & res , int n , int & num ) { if ( n == 0 ) { res . push_back ( num ) ; return ; } grayCodeUtil ( res , n - 1 , num ) ; num = num ^ ( 1 << ( n - 1 ) ) ; grayCodeUtil ( res , n - 1 , num ) ; } vector < int > grayCodes ( int n ) { vector < int > res ; int num = 0 ; grayCodeUtil ( res , n , num ) ; return res ; } int main ( ) { int n = 3 ; vector < int > code = grayCodes ( n ) ; for ( int i = 0 ; i < code . size ( ) ; i ++ ) cout << code [ i ] << endl ; return 0 ; }