Tutorialspoint.dev

A backtracking approach to generate n bit Gray Codes

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


This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter