An n-bit gray code sequence is a sequence of 2^n integers where:

  • Every integer is between 0 and 2^n - 1 (inclusive)
  • The first integer is 0
  • An integer appears at most once in the sequence
  • The binary representation of every pair of adjacent integers differs by exactly one bit
  • The binary representation of the first and last integers differs by exactly one bit

Given an integer n, return any valid n-bit gray code sequence.

Examples

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of the gray code sequence is [00, 01, 11, 10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit  
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00, 10, 11, 01].

Example 2:

Input: n = 1
Output: [0,1]

Constraints

  • 1 <= n <= 16

Thinking Process

There are several approaches to generate Gray codes:

  1. Backtracking: Try all possible sequences and backtrack when invalid
  2. Recursive Construction: Build Gray code recursively by mirroring previous sequence
  3. Iterative Construction: Build Gray code iteratively using the same mirroring principle
  4. Mathematical Formula: Use the formula i ^ (i >> 1) for each number
Backtracking tree start choose → explore → undo (prune)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Choose / explore / unchoose (this problem) O(2^n) O(n) Subsets, combinations
Constraint pruning Reduced search O(n) Early exit on invalid partial
Sort + skip duplicates O(2^n) O(n) Combination sum II style
Path recording O(n!) worst O(n) Permutations

Solution

class Solution:
    def grayCode(self, n: int) -> list[int]:
        result = [0]
        is_present = {0}
        self.getGrayCode(result, n, is_present)
        return result

    def getGrayCode(self, result: list[int], n: int, is_present: set[int]) -> bool:
        if len(result) == (1 << n):
            return True
        current = result[-1]
        for i in range(n):
            next_num = current ^ (1 << i)
            if next_num not in is_present:
                is_present.add(next_num)
                result.append(next_num)
                if self.getGrayCode(result, n, is_present):
                    return True
                is_present.remove(next_num)
                result.pop()
        return False

Solution Explanation

Approach: Choose / explore / unchoose (this problem)

Key idea: There are several approaches to generate Gray codes:

How the code works:

  1. Backtracking: Try all possible sequences and backtrack when invalid
  2. Recursive Construction: Build Gray code recursively by mirroring previous sequence
  3. Iterative Construction: Build Gray code iteratively using the same mirroring principle
  4. Mathematical Formula: Use the formula i ^ (i >> 1) for each number

Walkthrough — input n = 2, expected output [0,1,3,2]:

The binary representation of the gray code sequence is [00, 01, 11, 10].

  • 00 and 01 differ by one bit
  • 01 and 11 differ by one bit
  • 11 and 10 differ by one bit
  • 10 and 00 differ by one bit [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00, 10, 11, 01].

    Common Mistakes

  1. Off-by-one errors in bit shifting (1 << (n-1) vs 1 << n)
  2. Forgetting to reverse the mirrored sequence
  3. Incorrect bit manipulation operations
  4. Not handling edge case n = 0 properly

References

Key Takeaways

  1. Mirror Property: Gray codes can be constructed by mirroring the previous sequence and adding a high-order bit
  2. Bit Manipulation: Use XOR (^) to flip bits and OR (|) to set bits
  3. Mathematical Formula: i ^ (i >> 1) directly computes the i-th Gray code
  4. Recursive Structure: Gray codes have a natural recursive structure