Strobogrammatic Number II

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"].

Hint:

1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Solution: recursion
Space complexity is stack space.

public class Solution {
    public List findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    public List helper(int remainLen, int n) {
        List res = new ArrayList();
        if (remainLen == 0) {
            return res;
        }
        if (remainLen == 1) {
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }
        if (remainLen == 2) {
            if (remainLen != n) {
                res.add("00");  // 00 is invalid
            }
            res.add("11");
            res.add("69");
            res.add("88");
            res.add("96");
            return res;
        }
        
        List sub = helper(remainLen - 2, n);
        for (int i = 0; i < sub.size(); i++) {
            String s = sub.get(i);
            if (remainLen != n) {
                res.add("0" + s + "0");  // 0不能被加到最高位
            }
            res.add("1" + s + "1");
            res.add("6" + s + "9");
            res.add("8" + s + "8");
            res.add("9" + s + "6");
        }
        Collections.sort(res);
        return res;
    }
}