Gray Code

A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length n.

Example:

Input: n = 2

Output:

00
01
11
10

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> ans, vis;

string to_str(int x, int n)
{
    string s;
    for (int i = 0; i < n; i++)
        s += (x >> i & 1) ? "1" : "0";
    reverse(s.begin(), s.end());
    return s;
}

void backtrack(int pos, int x, int n)
{
    vis[x] = 1;
    ans.push_back(x);
    if (pos == (1 << n) - 1)
    {
        for (int nx : ans)
            cout << to_str(nx, n) << "\n";
        exit(0);
    }
    for (int i = 0; i < n; i++)
    {
        int nx = x ^ (1 << i);
        if (vis[nx])
            continue;
        backtrack(pos + 1, nx, n);
        vis[nx] = 0;
        ans.pop_back();
    }
}

void grayCode(int n)
{

    vis.assign(1 << n, 0);
    backtrack(0, 0, n);
}

int main()
{
    int n = 2;

    grayCode(n);

    return 0;
}