# 0247. Strobogrammatic Number II

<https://leetcode.com/problems/strobogrammatic-number-ii>

## Description

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`

## ac1：iterative

```java
class Solution {
    public List<String> findStrobogrammatic(int n) {
        if (n == 0) return new ArrayList<String>();

        List<String> odd = Arrays.asList("0", "1", "8");
        List<String> even = Arrays.asList("11","69","88","96");

        for (int i = 3; i <= n; i++) {
            if (i == 4) even = Arrays.asList("00", "11","69","88","96");
            List<String> curr = i % 2 == 0 ? even : odd;

            List<String> tmp = new ArrayList<String>();
            for (int j = 0; j < curr.size(); j++) {
                String s = curr.get(j);
                if (i < n) tmp.add("0" + s + "0");
                tmp.add("1" + s + "1");
                tmp.add("8" + s + "8");
                tmp.add("6" + s + "9");
                tmp.add("9" + s + "6");
            }

            if (i % 2 == 0) {
                even = tmp;
            } else {
                odd = tmp;
            }
        }

        return n % 2 == 0 ? even : odd;
    }
}
```

## ac2: recursive

```java
class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }

    private List<String> helper(int k, int last) {
        //exit
        if (k == 0) return Arrays.asList("");
        if (k == 1) return Arrays.asList("0","1","8");

        // get base, append like: "8"+x+"8"
        List<String> base = helper(k - 2, last);
        List<String> tmp = new ArrayList<String>();
        for (int i = 0; i < base.size(); i++) {
            String s = base.get(i);
            if (k != last) tmp.add("0"+s+"0");
            tmp.add("1"+s+"1");
            tmp.add("8"+s+"8");
            tmp.add("6"+s+"9");
            tmp.add("9"+s+"6");
        }

        // return new list
        return tmp;
    }
}
/**
how to write a recursion
1. definition, parameters, do what, return what
2. reduce parameter
3. exit, return

**/
```