Each path of DFS is a valid combination. We can solve the problem by enumerating every path.
I use deep first search (DFS) idea. Is there any better solutions?

@jarc, @atul4mlko, what language do you use? 12ms seems cpp. However, java can never be that fast.

I used BSF search and implemented it with recursion in C++. And my runtime was 4ms. The cost of time is quite related to the language we use but I don't think it means too much if we have similar time complexity.
class Solution { public: vector<string> letterCombinations(string digits) { unordered_map<char, string> phone_pad; //build hash table phone_pad['2']= "abc"; phone_pad['3']= "def"; phone_pad['4']= "ghi"; phone_pad['5']= "jkl"; phone_pad['6']= "mno"; phone_pad['7']= "pqrs"; phone_pad['8']= "tuv"; phone_pad['9']= "wxyz"; vector<string> result; //string current = phone_pad[digits[0]]; if (digits.size() == 0) { //in case the input is "" result.push_back(""); return result; } string current = phone_pad[digits[0]]; if (digits.size() == 1) { //close condition for recursion for (int i = 0; i < current.size(); ++i) { string tmp = ""; tmp.push_back(current[i]); result.push_back(tmp); } return result; } string next = digits.substr(1, digits.size()  1); vector<string> iter = letterCombinations(next); //recursion for sub string and combine the result for (int i = 0; i < current.size(); ++i) { for (int j = 0; j < iter.size(); ++j) { string tmp = ""; tmp.push_back(current[i]); result.push_back((tmp + iter[j])); } } return result; } };

in 4ms for 25/25
class Solution { public: unordered_map<char, string> dig2char; Solution() { dig2char['2'] = "abc"; dig2char['3'] = "def"; dig2char['4'] = "ghi"; dig2char['5'] = "jkl"; dig2char['6'] = "mno"; dig2char['7'] = "pqrs"; dig2char['8'] = "tuv"; dig2char['9'] = "wxyz"; } vector<string> letterCombinations(string digits) { vector<string> result; if ( digits.size() == 0 ) { result.push_back(""); return result; } vector<string> temp = letterCombinations(digits.substr(1)); for(int j = 0; j < dig2char[digits[0]].size(); j ++) for(int t = 0; t < temp.size(); t ++ ) result.push_back(dig2char[digits[0]][j] + temp[t]); return result; }
};

I think I got a brief solution, it is not recursive. But I believe it is BFS search. I think every solution should search all the paths. So your solution is good enough.
Here is my solution:class Solution { public: vector<string> letterCombinations(string digits) { //the s[n] means that the first letter of the button n is the (s[n])th letter in alphabet //eg. s[2] means that the first letter of the button 2 is the 0th letter in alphabet which is 'a' int s[]={0,0,0,3,6,9,12,15,19,22,26}; //push an empty string, this may cause error if digits is empty :) vector<string> result(1); for(int i=0;i<digits.length();i++){ vector<string> temp_vec; //for every string, append a new letter for(int j=0;j<result.size();j++){ int n=digits[i]'1'+1;//get the button number for(int k=s[n];k<s[n+1];k++) temp_vec.push_back(result[j]+char('a'+k));//append a new letter } result=temp_vec; } return result; } };

Just an another solution that may inspire, with no recursion. Consider a string to be a large number with heterogenous base for each position, then just enumerate all of it, and do base conversion, also 4ms:
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> ans; size_t m = 1, n = digits.size(); for (auto &c: digits) m *= dict[c  '0'].length(); for (size_t i = 0; i < m; i ++) { size_t p = i; string s = ""; for (size_t j = 0; j < n; j ++) { int c = digits[j]  '0'; int base = dict[c].length(); int v = p % base; s += dict[c][v]; p /= base; } ans.push_back(s); } return ans; } };

yes ,it's really bfs.in your solution you just enum you ret level by level,get the final ret in the finally loop