Backtracking - Gray Code

An n-bit Gray code sequence is a sequence of 2^n integers where every consecutive pair of values differs by exactly one bit. Given n, return any valid n-bit Gray code sequence starting from 0.

Input: n = 2 → Output: [0,1,3,2]

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

Use the reflection/induction approach: for n bits, the Gray code is built by taking the n-1 bit sequence, mirroring it, and prepending 0 to the original and 1 to the mirror. Equivalently, the i-th Gray code is i ^ (i >> 1).

For each integer i from 0 to 2^n - 1, compute i XOR (i >> 1).
This formula directly gives the Gray code at position i.
The resulting list automatically ensures adjacent entries differ by one bit.

import java.util.*; class Solution { public List<Integer> grayCode(int n) { List<Integer> result = new ArrayList<>(); for (int i = 0; i < (1 << n); i++) { result.add(i ^ (i >> 1)); } return result; } }

Time Complexity: O(2^n)
Space Complexity: O(1) extra (result list is the output)