class Solution {
 public:
  vector<string> findStrobogrammatic(int n) {
    return helper(n, n);
  }

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

    vector<string> ans;

    for (const string& inner : helper(n - 2, k)) {
      if (n < k)
        ans.push_back("0" + inner + "0");
      ans.push_back("1" + inner + "1");
      ans.push_back("6" + inner + "9");
      ans.push_back("8" + inner + "8");
      ans.push_back("9" + inner + "6");
    }

    return ans;
  }
};

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

  private List<String> helper(int n, int k) {
    if (n == 0)
      return new ArrayList<>(Arrays.asList(""));
    if (n == 1)
      return new ArrayList<>(Arrays.asList("0", "1", "8"));

    List<String> ans = new ArrayList<>();

    for (final String inner : helper(n - 2, k)) {
      if (n < k)
        ans.add("0" + inner + "0");
      ans.add("1" + inner + "1");
      ans.add("6" + inner + "9");
      ans.add("8" + inner + "8");
      ans.add("9" + inner + "6");
    }

    return ans;
  }
}

class Solution:
  def findStrobogrammatic(self, n: int) -> List[str]:
    def helper(n: int, k: int) -> List[str]:
      if n == 0:
        return ['']
      if n == 1:
        return ['0', '1', '8']

      ans = []

      for inner in helper(n - 2, k):
        if n < k:
          ans.append('0' + inner + '0')
        ans.append('1' + inner + '1')
        ans.append('6' + inner + '9')
        ans.append('8' + inner + '8')
        ans.append('9' + inner + '6')

      return ans

    return helper(n, n)