给定一个整数 n ，返回所有长度为 n 的 中心对称数 。你可以以 任何顺序 返回答案。
中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。
示例 1:
输入：n = 2
输出：[“11”,“69”,“88”,“96”]
示例 2:
输入：n = 1
输出：[“0”,“1”,“8”]
提示：
1 <= n <= 14
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/strobogrammatic-number-ii
方法一：回溯法
C++提交内容：
class Solution {
private:
unordered_map<char, char> m = {
{'0', '0'},
{'1', '1'},
{'6', '9'},
{'8', '8'},
{'9', '6'}
};
vector<string> ans;
public:
void dfs(string s, int n) {
if (s.length() == n) {
if ((s[0] != '0' && n > 1) || n == 1) ans.push_back(s);
return;
}
unordered_map<char, char>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
s = iter->first + s + iter->second;
dfs(s, n);
s = s.substr(1, s.length() - 2);
}
}
vector<string> findStrobogrammatic(int n) {
if (n % 2 == 0) {
dfs("", n);
}
else {
dfs("0", n);
dfs("1", n);
dfs("8", n);
}
return ans;
}
};