public static List<Integer> grayCode(int n) {
if (n < 0)
return new ArrayList<Integer>();
if (n == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(0);
return list;
}
List<Integer> tmp = grayCode(n  1);
List<Integer> result = new ArrayList<Integer>(tmp);
int addNumber = 1 << (n  1);
for (int i = tmp.size()  1; i >= 0; i) {
result.add(addNumber + tmp.get(i));
}
return result;
}
JAVAEasy Version To Understand!!!!!!


I try to explain a little bit...
n = 0: 0 n = 1: 0, 1 n = 2: 00, 01, 11, 10 (0, 1, 3, 2) n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)
Take n=3 as the example, the first four sequences are exactly same as n=2 sequences.
The second four sequences are derived of the following steps: reverse n=3 first half sequence: 010, 011, 001, 000
 Add 2^2 to each element of reversed n=2 sequence
Now we can extend to n=i situation.
The first half of n=i is the same sequence as n=i1
The second half of n=i is add 2^(i1) to the reversed sequence of first half.Reference: http://bangbingsyb.blogspot.com/2014/11/leetcodegraycode.html

C++ Equivalent code
class Solution { vector<int> result; public: vector<int> grayCode(int n) { vector<int> result; if(n<0) return result; if(n==0) {result.push_back(0); return result;} result = grayCode(n1); //cout<<result.size(); int x=1<<n1; for(int i=result.size()1;i>=0;i) { result.push_back(x+result[i]); } return result; } };

I come up with a similar solution, and it's more concise. Please check it out.
/* n = 0: 0 n = 1: 0  1 n = 2: 00, 01  11, 10 n = 3: 000, 001, 011, 010  110, 111, 101, 100 f(n) = f(n  1)  2 ^ (n  1) + f(n  1) */ public class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new ArrayList<>(); res.add(0); for(int i = 1; i <= n; i++) { int size = res.size(), base = 1 << (i  1); for(int j = size  1; j >= 0; j) { res.add(base + res.get(j)); } } return res; } }