import math
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        allowedDiffs = [int(1*math.pow(2,i)) for i in range(0,n)]
        grayCodes = [0]
        for diff in allowedDiffs:
            grayCodes += [code + diff for code in reversed(grayCodes)]
        return grayCodes
class Solution {
    public List<Integer> grayCode(int n) {
      ArrayList list=new ArrayList();
       for(int i=0;i<(1<<n);i++){
         list.add(i^(i>>1));
       }
         return list;
    }
}
Gray Code
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.

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 16


/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    return binaryToInt(dfs(n, ['0', '1']))
};

const dfs = (n, arr) => {
    if (n === 1) return arr

    const revArr = [...arr].reverse()

    addOneBefore('0', arr)
    addOneBefore('1', revArr)

    return dfs(n - 1, [...arr, ...revArr])
}

const addOneBefore = (e, arr) => {
    for (let i = 0; i < arr.length; i++) {
        arr[i] = e + arr[i]
    }
}

const binaryToInt = (arr) => {
    for (let i = 0; i < arr.length; i++){
        arr[i] = parseInt(arr[i], 2)
    }
    return arr
}
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> dp = {0,1};
        int cnt = 1;
        for(int i = 2; i < n+1; i++) {
            int mod = pow(2, cnt);
            int index = dp.size()-1;
            while(index >= 0) {
                dp.push_back(dp[index] + mod);
                index--;
            }
            cnt++;
        }
        return dp;
    }
};