Leetcode 89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

题意：给出数字n，代表一个数字最多占n个bit，数字从0开始的话，每次最多可以改变一个bit（从0到1或从1到0），要求返回一个最长的变换序列，中间变换不能有重复。

这道题自己尝试从深度优先搜索和位操作的思路考虑，都没有想出来。看了discuss，中间有一个解法建单易懂。
如果已知n-1位的序列，那么n位的序列求法是有规律的，比如2位的序列[00,01,11,10]变成3位的话只需要先在高位加0变成[000,001,011,010]，再逆序在高位加1，即[110,111,101,100]，合起来就是3位的序列了，[000,001,011,010,110,111,101,100]。

public List<Integer> grayCode(int n) {
    List<Integer> rs=new ArrayList<Integer>();
    rs.add(0);
    for(int i=0;i<n;i++){
        int size=rs.size();
        for(int k=size-1;k>=0;k--)
            rs.add(rs.get(k) | 1<<i);
    }
    return rs;
}