Thinking process

find the pattern

• the gray code sequence of n can be generated from the sequence of n - 1
• n = 2 => 00 01 11 10
• n = 3 => add 0 at the highest bit, 000, 001, 011, 010; then add 1 at the highest position but reverse the elements, 110, 111, 101, 100

Mistakes

don't need to create two lists, one list is enough, since the adding 0 won't affect the value

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

        for (int i = 1; i <= n; ++i) {
            int len = result.size();
            for (int j = len - 1; j >= 0; --j) {
                result.add(result.get(j) | 1 << (i - 1));
            }
        }

        return result;
    }
}