> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0089-gray-code.md).

# 0089. Gray Code

<https://leetcode.com/problems/gray-code>

## Description

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

* Every integer is in the **inclusive** range `[0, 2n - 1]`,
* The first integer is `0`,
* An integer appears **no more than once** in the sequence,
* The binary representation of every pair of **adjacent** integers differs by **exactly one bit**, and
* 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***.

**Example 1:**

```
**Input:** n = 2
**Output:** [0,1,3,2]
**Explanation:**
The binary representation of [0,1,3,2] 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].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit
```

**Example 2:**

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

**Constraints:**

* `1 <= n <= 16`

## ac1

This one is like dp + bit manipulation, nothing like backtracking.

```java
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(0);

        // like dp
        for (int i = 0; i < n; i++) {
            int len = res.size();
            for (int j = len-1; j >= 0; j--) {
                int tmp = res.get(j) | 1 << i;
                res.add(tmp);
            }
        }

        return res;
    }
}
```

## ac2

this is more intuitive, more backtracking.

```java
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        // edge cases
        if (n <= 0) {
            res.add(0);
            return res;
        }
        backtrack("", n, true, res);
        return res;
    }

    private void backtrack(String prefix, int remain, boolean up, List<Integer> res) {
        if (remain == 0) {
            int tmp = Integer.parseInt(prefix, 2);
            res.add(tmp);
            return;
        }

        if (up) {
            backtrack(prefix+"0", remain-1, true, res);
            backtrack(prefix+"1", remain-1, false, res);
        } else {
            backtrack(prefix+"1", remain-1, true, res);
            backtrack(prefix+"0", remain-1, false, res);
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0089-gray-code.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.