A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

一刷
题解：recursion, 每次n减少2，并从首尾append

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    private List<String> helper(int n, int m){
        List<String> res = new ArrayList<>();
        if(n == 0){
            res.add("");
            return res;
        }
        if(n == 1){
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }
        
        List<String> list = helper(n-2, m);
        for(int i=0; i<list.size(); i++){
            String s = list.get(i);
            if(n!=m) res.add("0" + s + "0");//not the last
            res.add("1" + s + "1");
            res.add("6" + s + "9");
            res.add("8" + s + "8");
            res.add("9" + s + "6");
        }
        return res;
    }
}