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.

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.

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