Problem 598627 · medium · Level 05 Advanced Algorithms & Graphs

A Cycle Through Every Bit Pattern

backtracking · bit manipulation · hamiltonian cycle

A rotary encoder must step through all 2**n settings 0 .. 2**n - 1 of an n-bit register, starting at 0, so that each step changes exactly one bit. After the last setting it wraps around to 0, and that wrap-around step must also change exactly one bit. Return any such ordering as a list of integers. Many orderings are valid; any correct one is accepted.

Examples

Input:  n = 1
Output: [0, 1]

Input:  n = 2
Output: [0, 1, 3, 2]
Explanation: 00 -> 01 -> 11 -> 10 -> back to 00, one bit per step.
            [0, 2, 3, 1] would be accepted too.

Constraints

  • 1 <= n <= 10

Goals

  • Search for an ordering by trying one-bit changes from the current value
  • Verify a closing condition when the ordering is complete
Starting Python…