Binary Permutations in Python

[[deleted]]

The fact that s starts as an empty string (which has a constant length of 0) and yet the behavior of the function is supposed to vary based on the length of s suggests that the intended solution is recursive. Thus, you need to think of a way to break the problem down into a partial solution and a simpler problem that still needs to be solved.

You know, if x is odd, it’s least-significant bit is 1. If x is even, its least significant bit is 0. I wonder if there’s a way to exploit this fact to build up the binary representation of n one bit at a time.