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

java class Solution { public List<Integer> grayCode(int n) { List<Integer> result = new ArrayList<>(); result.add(0); for (int i = 0; i < n; i++) { int size = result.size(); for (int j = size - 1; j >= 0; j--) { result.add(result.get(j) | (1 << i)); } } return result; } }

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