Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: n = 2
Output: ["11","69","88","96"]
Example 2:
Input: n = 1
Output: ["0","1","8"]
Constraints:
1 <= n <= 14
Solutions
Solution 1: Recursion
If the length is $1$, then the strobogrammatic numbers are only $0, 1, 8$; if the length is $2$, then the strobogrammatic numbers are only $11, 69, 88, 96$.
We design a recursive function $dfs(u)$, which returns the strobogrammatic numbers of length $u$. The answer is $dfs(n)$.
If $u$ is $0$, return a list containing an empty string, i.e., [""]; if $u$ is $1$, return the list ["0", "1", "8"].
If $u$ is greater than $1$, we traverse all the strobogrammatic numbers of length $u - 2$. For each strobogrammatic number $v$, we add $1, 8, 6, 9$ to both sides of it, and we can get the strobogrammatic numbers of length u.
Note that if $u \neq n$, we can also add $0$ to both sides of the strobogrammatic number.
Finally, we return all the strobogrammatic numbers of length $n$.