# 247. Strobogrammatic Number II¶

• Time: $O(5^n)$
• Space: $O(|\texttt{ans}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: vector findStrobogrammatic(int n) { return helper(n, n); } private: vector helper(int n, int k) { if (n == 0) return {""}; if (n == 1) return {"0", "1", "8"}; vector 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public List findStrobogrammatic(int n) { return helper(n, n); } private List 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 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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)