247. Strobogrammatic Number II

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new ArrayList<>();
        char[] cur = new char[n];
        findStrobogrammatic(0, n - 1, cur, res);
        return res;
    }
    
    private void findStrobogrammatic(int left, int right, char[] cur, List<String> res) {
        if (left > right) {
            res.add(new String(cur));
            return;
        }
        if (left == right) {
            cur[left] = '0';
            res.add(new String(cur));
            cur[left] = '1';
            res.add(new String(cur));
            cur[left] = '8';
            res.add(new String(cur));
            return;
        }
        
        if (left != 0) {
            cur[left] = '0';
            cur[right] = '0';
            findStrobogrammatic(left + 1, right - 1, cur, res);
        }

        cur[left] = '1';
        cur[right] = '1';
        findStrobogrammatic(left + 1, right - 1, cur, res);        
        cur[left] = '6';
        cur[right] = '9';
        findStrobogrammatic(left + 1, right - 1, cur, res);       
        cur[left] = '8';
        cur[right] = '8';
        findStrobogrammatic(left + 1, right - 1, cur, res);       
        cur[left] = '9';
        cur[right] = '6';
        findStrobogrammatic(left + 1, right - 1, cur, res);       
    }
}

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