247. Strobogrammatic Number II

Follow the tips, I realized that this problem can be solved by backtracking. I was trying to design the backtracking API to include the final result. But it turns out not working and can complicate the solution. So I followed the API of top rated solution, i.e. the backtracking function returns the result. Also, it is important to do backtracking with n-2 not n-1.

1:  class Solution {  
2:  public:  
3:    vector<string> findStrobogrammatic(int n) {  
4:      return helper(n, n);  
5:    }  
6:    vector<string> helper(int n, int m) {  
7:      if (n == 0) return vector<string> {""};  
8:      if (n == 1) return vector<string> {"0", "1", "8"};  
9:      vector<string> tmp = helper(n-2, m), res;  
10:      for (int i = 0; i < tmp.size(); i++) {  
11:        if (n != m) res.push_back("0" + tmp[i] + "0");  
12:        res.push_back("1" + tmp[i] + "1");  
13:        res.push_back("8" + tmp[i] + "8");  
14:        res.push_back("6" + tmp[i] + "9");  
15:        res.push_back("9" + tmp[i] + "6");  
16:      }  
17:      return res;  
18:    }  
19:  };