Given a number n, the task is to generate n bit Gray codes (generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit)

Examples:

Input : 2 Output : 0 1 3 2 Explanation : 00 - 0 01 - 1 11 - 3 10 - 2 Input : 3 Output : 0 1 3 2 6 7 5 4

We have discussed an approach in Generate n-bit Gray Codes

This article provides a **backtracking approach** to the same problem. Idea is that for each bit out of n bit we have a choice either we can ignore it or we can invert the bit so this means our gray sequence goes upto 2 ^ n for n bits. So we make two recursive calls for either inverting the bit or leaving the bit as it is.

`// CPP program to find the gray sequence of n bits. ` `#include <iostream> ` `#include <vector> ` `using` `namespace` `std; ` ` ` `/* 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. */` `void` `grayCodeUtil(vector<` `int` `>& res, ` `int` `n, ` `int` `& num) ` `{ ` ` ` `// base case when we run out bits to process ` ` ` `// we simply include it in gray code sequence. ` ` ` `if` `(n == 0) { ` ` ` `res.push_back(num); ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// ignore the bit. ` ` ` `grayCodeUtil(res, n - 1, num); ` ` ` ` ` `// invert the bit. ` ` ` `num = num ^ (1 << (n - 1)); ` ` ` `grayCodeUtil(res, n - 1, num); ` `} ` ` ` `// returns the vector containing the gray ` `// code sequence of n bits. ` `vector<` `int` `> grayCodes(` `int` `n) ` `{ ` ` ` `vector<` `int` `> res; ` ` ` ` ` `// num is passed by reference to keep ` ` ` `// track of current code. ` ` ` `int` `num = 0; ` ` ` `grayCodeUtil(res, n, num); ` ` ` ` ` `return` `res; ` `} ` ` ` `// Driver function. ` `int` `main() ` `{ ` ` ` `int` `n = 3; ` ` ` `vector<` `int` `> code = grayCodes(n); ` ` ` `for` `(` `int` `i = 0; i < code.size(); i++) ` ` ` `cout << code[i] << endl; ` ` ` `return` `0; ` `} ` |

Output:

0 1 3 2 6 7 5 4

## leave a comment

## 0 Comments