89. Gray Code (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        # math
        result = [0]
        for i in range(n):
            temp = []
            mask = 1 << i
            for num in reversed(result):
                temp.append(mask ^ num)
            result += temp
        return result
        
        # dfs
        self.result = []
        m = 2 ** n
        def dfs(res, seen):
            if len(res) < m:
                for i in range(n):
                    mask = 1 << i
                    x = res[-1] ^ mask
                    if x not in seen:
                        res.append(x)
                        seen.add(x)
                        dfs(res, seen)
            else:
                self.result = res
        dfs([0], {0})
        return self.result