<p>An <strong>n-bit gray code sequence</strong> is a sequence of <code>2<sup>n</sup></code> integers where:</p>

<ul>
	<li>Every integer is in the <strong>inclusive</strong> range <code>[0, 2<sup>n</sup> - 1]</code>,</li>
	<li>The first integer is <code>0</code>,</li>
	<li>An integer appears <strong>no more than once</strong> in the sequence,</li>
	<li>The binary representation of every pair of <strong>adjacent</strong> integers differs by <strong>exactly one bit</strong>, and</li>
	<li>The binary representation of the <strong>first</strong> and <strong>last</strong> integers differs by <strong>exactly one bit</strong>.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>any valid <strong>n-bit gray code sequence</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> [0,1,3,2]
<strong>Explanation:</strong>
The binary representation of [0,1,3,2] is [00,01,11,10].
- 0<u>0</u> and 0<u>1</u> differ by one bit
- <u>0</u>1 and <u>1</u>1 differ by one bit
- 1<u>1</u> and 1<u>0</u> differ by one bit
- <u>1</u>0 and <u>0</u>0 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- <u>0</u>0 and <u>1</u>0 differ by one bit
- 1<u>0</u> and 1<u>1</u> differ by one bit
- <u>1</u>1 and <u>0</u>1 differ by one bit
- 0<u>1</u> and 0<u>0</u> differ by one bit
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> [0,1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 16</code></li>
</ul>

class Solution:
    def grayCode(self, n: int) -> List[int]:

        first_zero = '0' * n
        first_one = ('0' * (n-1)) + '1' 
        res_str = [first_zero, first_one]

        for i in range(n - 2, -1, -1):
            print(res_str)
            for s in res_str[::-1]:
                new_s = s[:i] + '1' + s[i+1:]
                res_str.append(new_s)

        res = []

        for i in res_str:
            res.append(int(i,2))
        
        return res
        



        

        

        '''
        reading:
        2^n integer
        every integer is in inclusive range

        first integer is 0
        every pair of adjacent integers differs by exactly one bit
        binary representation of first and last integers differs by one bit

        valid n-bit gray code sequence

        brute force:

        differs by exactly one bit?
        binary representation
        wise

        absolutely nothign is coming to mind
        how to make integers differ by one bit reprsentation wise

        deal with strings pretty much
        how to make strings off by 1
        to generate all combinations 
        at each index can be 0 or 1
        2^n to generate all combinations
        how to order them together?
        count number of one's

        and put counts with each other
        no that wouldn't work

        can i solve this with a dynamic programming?

        simple backtracking tree?
        n = 3
        000
        001
        010
        111
        101


        10011
        00111

        0000
        1000
        1100
        1110
        1111

        0111
        0011
        0001

        0000
        0001
        0011
        0010
        0110
        0111
        0101
        0100
        1100
        1101
        1111
        1110
        1010
        1011
        1001
        1000
        

        figured it out after doing some examples
        sort of building up to index
        then reverse and add next digit



        '''
        
25000