1 回溯算法（Java实现）

/*方法：回溯搜索算法 + HashMap/一维数组 映射难度：中等思路：使用回溯算法遍历决策树，穷举所有解，决策树的每个节点维护当前已选路径track/path和选择列表等信息。本题中，电话号码digits确定了各个数字的出现顺序（每个数字对应不同字母）。对电话号码每个数字的可能字母进行穷举组合。使用HashMap或一维数组，存储数字与不同字母的映射关系。时间复杂度：空间复杂度：类似题目：t077-组合区别：t077-组合中，数字的顺序是任意的且不重复的，使用start/index索引排除已选的数字。t017-电话号码的字母组合中，电话号码每个数字的顺序已确定，按数字顺序对相应字符进行组合。使用start/index索引确定第i个数字，并选择某个对应字符。
*/import java.util.ArrayList;
import java.util.List;public class Solution {//结果集List<String> res = new ArrayList<>();//数字与字母的映射关系private String[] digitMap = new String[]{"",     "",     "abc",  //0 1 2"def",  "ghi",  "jkl",  //3 4 5"mno",  "pqrs", "tuv",  //6 7 8"wxyz"                  //9};public List<String> letterCombinations(String digits) {//边界特判if(digits.length() == 0 || digits == null) return res;//记录已选择的字母StringBuilder track = new StringBuilder();//调用回溯函数backtrack(digits, 0, track);return res;}//回溯函数//路径：track中已记录的字符//选择列表：由号码digits和索引start确定当前的数字（对应的字母）//结束条件：track的大小和号码digits的长度相同private void backtrack(String digits, int start, StringBuilder track) {//触发结束条件if(track.length() == digits.length()){res.add(track.toString());//res.add(new String(track));return;}//根据索引start获取号码的当前数字char digit = digits.charAt(start);//遍历数字对应的各个字母for(char ch : digitMap[digit - '0'].toCharArray()){//作出选择track.append(ch);//递归调用回溯函数 → 进入决策树的下一层backtrack(digits, start + 1, track);//撤销选择track.deleteCharAt(track.length() - 1);}}
}

2 回溯算法（C++实现）-待更新