247

class Solution {
    int _n;
    vector<pair<char, char>> candidates = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6','9'}, {'9','6'}};

    vector<string> helper(int n) {
        vector<string> res;
        if (n == 0) return {{}};
        if (n == 1) return {"0", "1", "8"};

        auto temp = helper(n-2);
        for (auto t : temp) {
            for (auto p : candidates) {
                if (_n != n || p.first != '0') {
                    string str = p.first + t + p.second;
                    res.push_back(str);
                }
            }
        }

        return res;
    }

public:
    vector<string> findStrobogrammatic(int n) {
        _n = n;
        return helper(n);
    }
};

-------------------------------------

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<string> ans;
        if(n <= 0)  return ans;
        string solution;
        for(int i = 0; i < n; i++) solution += "0";
        int l = 0, r = n-1;
        dfs(l,r,solution,ans);
        return ans;
    }

    void dfs(int l, int r, string solution, vector<string>& ans){
        if(l == r){
            solution[l] = '0';
            ans.push_back(solution);
            solution[l] = '1';
            ans.push_back(solution);
            solution[l] = '8';
            ans.push_back(solution);
            return;
        }
        else if(l > r){
            ans.push_back(solution);
            return;
        }

        solution[l] = solution[r] = '1';
        dfs(l+1,r-1,solution,ans);
        solution[l] = solution[r] = '8';
        dfs(l+1,r-1,solution,ans);
        solution[l] = '6', solution[r] = '9';
        dfs(l+1,r-1,solution,ans);
        solution[l] = '9', solution[r] = '6';
        dfs(l+1,r-1,solution,ans);
        if(l != 0){
            solution[l] = solution[r] = '0';
        dfs(l+1,r-1,solution,ans);
        }
    }
};