# 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);
        }
    }
}
```