247. Strobogrammatic Number II

T: O(N + (N-2) + (N-4) + (N-6) ... + 0)

S: O(N/2)

```java
class Solution {
    private String[][] defaultStr = {{"0","0"}, {"1","1"}, {"6", "9"}, {"8", "8"}, {"9", "6"}};
    List<String> one = Arrays.asList("0","1","8");
    public List<String> findStrobogrammatic(int n) {
        return dfs(n, n);
    }
    private List<String> dfs(int n, int originalN) {
        if (n == 0) {
            return Arrays.asList("");
        }
        if (n == 1) {
            return one;
        }
        List<String> inner = dfs(n - 2, originalN);
        List<String> result = new ArrayList<>();
        
        for (int i = 0; i < defaultStr.length; i++) {
            for (String innerStr : inner) {
                StringBuilder sb = new StringBuilder();
                if (n == originalN && i == 0) {
                    continue;
                }
                sb.append(defaultStr[i][0]).append(innerStr).append(defaultStr[i][1]);
                result.add(sb.toString());
            }
        }
        return result;
    }
}

/**


969

0 1 8 

1x1 

6x9

8x8

9x6


f(4) = 2 + f(2)

8698

 */
```