给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
提示：
0<= digits.length<= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
该方法较好理解
如例子“23”
先将2对应的a，b，c加入队列，然后每次将a pop出队列时，将a分别与3对应的def分别组合加入队列。
代码如下：
class Solution {public:
vectorletterCombinations(string digits)
{vectorres;
string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
queueq;
int n=digits.size();
for(int i=0;iif(q.empty())
{for(int j=0;jwhile(q.front().size()for(int j=0;jstring e=q.front()+s[digits[i]-'0'].substr(j,1);
q.push(e);
}
q.pop();
}
}
}
while(!q.empty())
{res.push_back(q.front());
q.pop();
}
return res;
}
}; 这个方法可能较为难理解
回溯其实可以理解为多条路分别走，你选择进入函数即走下一步，不进入函数往下走就是换个方向走，还没到下一步。
这里讲一讲回朔法的思路：1这一步要干嘛，2下一步要干嘛，3目的是什么
使用回溯法最好要能画成n叉树的结构，树的宽度就用for循环，深度就用递归。
另外回溯法要注意进入下一层递归时某些值才改变，可以在调用自身的括号中改变，不能在调用前面改变
如果不能在括号中改变，可以这样
for(int i=idx;iif(candidates[i]>target-sum) continue;
if(candidates[i]<=target-sum)
{v.push_back(candidates[i]);
function(target,sum+candidates[i],candidates,v,i);
v.pop_back();
}
} push之后再pop这样就不会对后面for循环操作造成影响
另外，在同一层的回溯数据是不变的，但是二维数组传进去就可以积累答案，因为后面对一维数组有回溯操作，所以保证数据不变，而对结果数组没有，所以结果数组可以积累。
注意如果要可以积累的话，要传入地址！！！！！！！！！
int也是，如果传入的是固定的值，就可以不用传入地址。
然后这一题配一张图更好理解
首先第一步是把第一个数字的字符加进去，第二步是把第二个数字的字符加进去，目的是将字符相加并放入数组中
故可以用函数加字符，同时这里每一个数字都要回溯，故还有用for循环
class Solution {public:
string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vectorres;
void v(string digits,string ss,int idx)
{ if(idx==digits.size()) res.push_back(ss);
else
{ string x=s[digits[idx]-'0'];
for(int i=0;iletterCombinations(string digits)
{if(digits.size()==0) return res;
v(digits,"",0);
return res;
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧