Gray Code (LeetCode Backtracking)

Question: 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

Idea: Gray code was invented in 1947. There are many ways of generating gray code. I just listed two methods as following:
Method 1: by reflection, use n=3 as an example.
n=2 gray code:             00    01   11    10
reflect:                                                            10    11    01     00
add 0 before first half: 000  001  011  010
add 1 before 2nd half:                                   110  111  101  100
n=2 gray code:             000  001   011  010  110  111  101  100

Method 2: by bit manipulation from binary to gray.
gray code=(binary>>1)^binary

Time: O(n^n) for reflection, O(2^n) for bit manipulation.
Space: O(1)

Code by Reflection:

 public class Solution {  
   public List<Integer> grayCode(int n) {  
     List<Integer> result=new ArrayList<Integer>();  
     if(n<=1)  
     {  
       for(int i=0;i<=n;i++)  
         result.add(i);  
       return result;  
     }  
     result=grayCode(n-1);  
     List<Integer> reflected=reflect(result);  
     int x=1<<(n-1);  
     for(int i=0;i<reflected.size();i++)  
       reflected.set(i,reflected.get(i)+x);  
     result.addAll(reflected);  
     return result;  
   }  
   public List<Integer> reflect(List<Integer> old)  
   {  
     List<Integer> result=new ArrayList<Integer>();  
     for(int i=old.size()-1;i>=0;i--)  
       result.add(old.get(i));  
     return result;  
   }  
 }  

Code by Bit Manipulation:

 public class Solution {  
   public int binaryToGray(int x)  
   {  
     return (x>>1)^x;  
   }  
   public List<Integer> grayCode(int n) {  
     List<Integer> result=new ArrayList<Integer>();  
     for(int i=0;i<Math.pow(2,n);i++)  
       result.add(binaryToGray(i));  
     return result;  
   }  
 }