# 0ms c++ solution using recursion

• Similar thought with Subset and Subset II and so on.

``````class Solution {
public:
int LetterNum(char digit){
if(digit == '9' || digit == '7')
return 4;
return 3;
}
bool helper(char lookup[8][4], string& digits, int start,
vector<string>& ret, string& go)
{
if(start >= digits.size())
return true;
if(digits[start] == '1') // if the digits string include '1', we will finally return an empty vector<string>
return false;
int width = LetterNum(digits[start]); // calculate one digit's lookup table size
for(int i = 0; i < width; i++)
{
go += lookup[digits[start]-0x32][i];
if(go.size() == digits.size())
ret.push_back(go);
else
if(!helper(lookup, digits, start+1, ret, go))
return false;
go.pop_back();
}
return true;
}

vector<string> letterCombinations(string digits) {
vector<string> ret;
if(digits.size() == 0)
return ret;
// build a lookup table;
char table[8][4] = {{'a','b','c'}, {'d','e','f'},{'g','h','i'}, {'j','k','l'},
{'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
string go;
if(helper(table, digits, 0, ret, go))
return ret;
return vector<string>();
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.