Solution of Gray

Approach #1

Start with the values [0, 1]. At each iteration, do the following:

• reverse the current list and append it to itself
• prepend each element in the first half with a 0
• prepend each element in the second half with a 1

The N^th iteration of this process generates all N bit configurations, in an order which respects the required property.

Haskell implementation

once applies a single iteration to a given list.
solve uses function composition to generate once composed to itself N-1 times, and applies the resulting function to the first iteration.

solve n = foldr (.) id (replicate (n-1) once) ["0", "1"]
once xs = map ('0':) xs ++ map ('1':) (reverse xs)

main = do
    input <- getContents
    let n = read input :: Int

    sequence $ map putStrLn $ solve n

Approach #2

Start from the null configuration. Try each of the N possible bit flips, and keep track of previously encountered configurations. When a new configuration is found, repeat the same process for it. Stop when no new configuration can be found.

Note: a recursive implementation of this approach can result in a stack overflow.