247. Strobogrammatic Number II
Problem
Find all strobogrammatic numbers of length n (look the same when rotated 180 degrees).
A strobogrammatic number is a number that looks the same when rotated 180 degrees (upside down). The digit pairs that are valid when rotated are:
- 0 → 0
- 1 → 1
- 6 → 9
- 8 → 8
- 9 → 6
Given an integer n, find all strobogrammatic numbers of length n. Return them as a list of strings in ascending order.
Examples
Input: 2
Output: ["11","69","88","96"]
Input: 1
Output: ["0","1","8"]
Hints
Use recursion or backtracking to build the number from center outward.
Handle odd and even length cases differently (center can be 0, 1, 8 for odd).
Valid pairs: (0,0), (1,1), (6,9), (8,8), (9,6).
Related Problems
247. Strobogrammatic Number II
Find all strobogrammatic numbers of length n (look the same when rotated 180 degrees).