Strobogrammatic Number II

Core idea: A strobogrammatic number is symmetric under a 180° rotation, so build it from the outside in — wrap a valid rotatable pair around a smaller strobogrammatic number, and only forbid the leading-0 pair at the outermost layer.

Problem, rephrased

You design glowing upside-down room numbers for a boutique hotel. A number is valid only if a guest who reads it while standing on their head sees a real number too. On the seven-segment style display, the only digits that survive a 180° flip are:

Every other digit (2,3,4,5,7) turns into nonsense, so it can never appear.

A whole number reads the same upside down when each digit at position i is the flip-partner of the digit at the mirror position. For example 69 flips to 69 (the 6 becomes a 9 on the right, the 9 becomes a 6 on the left), and 818 flips to 818.

Task: Given a length n, return all such numbers that have exactly n digits. Order does not matter.

We return strings, not integers, because leading zeros matter to the shape but a number like 0110 is not a valid 4-digit number — more on that below.