[LeetCode] 89. Gray Code

Problem :  https://leetcode.com/problems/gray-code/

Use DFS approach to find all valid codes.

Time Complexity  =  O ( 2 ** n )

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        
        result = [0,1]
        memo = set(result)
        
        last = 1
        
        while last != 0:
            num = last
            last = 0
            
            mask = 1
            
            # iterate each bit position to find the next number
            for i in range(n):
                tmp = num ^ (mask << i)
                
                if tmp not in memo:
                    memo.add(tmp)
                    result.append(tmp)
                    last = tmp
                    break
    
        return result