## Strobogrammatic Number II

• Time:O(5^n)
• Space:O(|\texttt{ans}|)

## C++

``````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;
}
};
``````

## JAVA

``````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)
}

return ans;
}
}
``````

## Python

``````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)
``````