LC89. Gray Code

class Solution:
    def grayCode(self, n: int) -> List[int]:
        """ O(2^N)/O(1)
        main idea: initialized number is all 0s with length of size n. change from lower digit to higher digit, start 
        """
        
        res = [0]
        for i in range(n):
            for j in range(len(res)-1,-1,-1):  # since there are one bit differ from last change, so we need to reverse iterate the results we have so far 
                res.append(res[j] | 1 << i) # update higer digit by set higher digit as 1 
                # res.append(res[j] + (1 << i))
        
        return res