A problem asks to find longest path in Hyper cube graph that visits each vertex at most once.

If two numbers have odd amount of bits in common then there is always a Hamiltonian path (length 2^n). Parity of common bits is checked using xor.

If parity is even then one can build a path of length 2^n - 1. This path can be built by
successively building Hamiltonian paths on lower dimension cube. That is, build a path of length 2^(n - 1) and recurse to find path of length 2^(n - 1) - 1.

So, the solution is built around knowing how to construct Hamiltonian path.

There is, in fact, a very simple approach. My algorithm works in O(2^n) and doesn't use extra memory.

So, i accidentally wrote a suboptimal solution for this problem (stored entire sequences of settings instead of just singular changes from the previous ones), saw it taking 15s (about 8 without the output) to complete max test on my laptop but submitted for fun anyway. Got AC in 0.4s. Go figure.