17. Letter Combinations of a Phone Number

A typical backtracking solution.

1:  class Solution {  
2:  private:  
3:    vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
4:  public:  
5:    vector<string> letterCombinations(string digits) {  
6:      vector<string> res;  
7:      if (digits.size() == 0) return res;  
8:      helper(digits, 0, "", res);  
9:      return res;  
10:    }  
11:    void helper(string &digits, int i, string sol, vector<string> &res) {  
12:      if (i == digits.size()) {  
13:        res.push_back(sol); return;  
14:      }  
15:      for (int j = 0; j < pad[digits[i]-'0'].size(); j++) {  
16:        sol += pad[digits[i]-'0'][j];  
17:        helper(digits, i+1, sol, res);  
18:        sol.pop_back();  
19:      }  
20:    }  
21:  };