继续刷LeetCode 热题 HOT 100 的题目，并且在博客更新我的solutions。在csdn博客中我会尽量用文字解释清楚，相关Java代码大家可以前往我的个人博客jinhuaiyu.com中查看。
今天的题目是典型的通过回溯法进行深度优先搜索，本质是暴力求解所有组合，而且这道题没有涉及剪枝，是最简单的回溯。but我真的好久没复习算法了，回溯都记不太清楚过程了……于是简单地又看了看。这道题挺适合我这种重新学习回溯的人。
题目：电话号码的字母组合
给定一个仅包含数字 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’] 的一个数字。
solution： 回溯/深度优先搜索
首先给出一个简单的搜索树：
根结点无意义，因为这道题没有固定的起始情况。输入的数字字符串每个数字其实就对应树的每一层的各个结点，每一种从第0层（不算根结点）到叶子结点的字符组合就是对应输入的数字字符串的一种结果。
这道题虽然答案显而易见（就是所有从第0层到叶子结点的路径），但是我们使用回溯去深度优先搜索一是程序更简单，二是以后碰到复杂的情况难以手动枚举时可以采用类似的思想。
这里我们通过递归进行回溯法，每一次递归都从当前层的某一个结点往下进行深度优先搜索，并在最后回溯到当前层，从而从当前层的另一个结点往下进行同样的搜索。这个回溯方法对于每一个子问题都是一样的搜索过程，按上面的图来说，就是如果输入的是“23”，那么2对应abc，原始问题可以通过递归转化为第一个字符是a或b或c，然后输入“3”，将对应的字符拼到a或b或c后面。
回溯方法的关键部分在搜索到了叶子结点或不符合的结点后（本题未体现）或者当前层节点全部搜索完后，当前深度优先搜索终止，回到上一层，此时要注意把刚刚搜索到叶子结点造成的状态更改全部改回到叶子节点层上一层的状态，即状态回溯。
递归回溯方法的伪代码如下：
void backtrack(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtrack(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
我们只要按着最普通的回溯去套本题即可。
带详细注释的java代码放在我的个人博客http://jinhuaiyu.com/leetcode-letter-combinations-of-a-phone-number/
