Gray Code Sequence

Problem

Return any valid n-bit Gray code sequence — a sequence of 2ⁿ integers where every consecutive pair (and the first/last pair) differ in exactly one bit.

Constraints

• 1 ≤ n ≤ 16

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def grayCode(self, n):
        return [i ^ (i >> 1) for i in range(1 << n)]

Java

import java.util.*;

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> out = new ArrayList<>();
        int total = 1 << n;
        for (int i = 0; i < total; i++) out.add(i ^ (i >> 1));
        return out;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.