给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
思路是回溯+递归，利用一个栈来存储字母。
具体实现就是，先用迭代存储一个字母，如果栈没满就递归并迭代存储字母，直到栈满再把栈里的内容扔到返回数组里，或者某个字母已经递归完了所有后续，就回到了上一层递归函数，把这个用过的字母pop出去，继续迭代 递归。
这里有个巨几把恶心的坑，就是我为少写几个参数在combine里用了static修饰的top和size，如果只测试一次，确实是没问题的，但是多测试几次就傻逼了啊！！！一开始我用了strcpy，给我报了个执行错误，特么地根本没头绪好吗，后来我自己写了个赋值，报了个空指针错误，妈的空你妹啊！！！还好聪明机智的我，最后还是发现了问题所在，花了快1小时的时间找一个“不存在的错误”。。。MMP。。。
唉，回想起来，以前总看见提示说什么什么，可能是你使用C/C++的全局变量，特么地我现在是真的印象深刻了！！！
/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ char *letter[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; int num[10]={0,0,3,3,3,3,3,4,3,4}; void combine(char** a,char* s,char* digits,int index,int len,int* top,int* size) { if(index==len) { int i; for(i=0;i<len;i++) a[*size][i]=s[i]; a[*size][i]=‘\0‘; (*size)++; return ; } int i,pos=digits[index]-‘0‘; for(i=0;i<num[pos];i++) { s[(*top)++]=letter[pos][i]; combine(a,s,digits,index+1,len,top,size); (*top)--; } } char** letterCombinations(char* digits, int* returnSize) { if(!*digits) return NULL; int len=strlen(digits); int i,size=1; for(i=0;i<len;i++) size*=num[(digits[i]-‘0‘)]; *returnSize=size; char **a=(char **)malloc(sizeof(char *)*size); len++; for(i=0;i<size;i++) a[i]=(char *)malloc(sizeof(char)*len); char *s=(char *)malloc(sizeof(char)*len); len--; int top=0,rear=0; combine(a,s,digits,0,len,&top,&rear); return a; }
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
原文：https://www.cnblogs.com/onlyandonly/p/9326210.html