# 题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

2：abc ，3：def。。。。8：tuv，9：wxyz

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

17. 电话号码的字母组合 - 力扣（LeetCode）

# 分析

首先把数字和字母用 map 或二维数组映射

然后惯例树状图

回溯三部曲：

1 确定回溯函数参数

字符串 s 保存叶子节点，字符串 result 保存每组结果

	vector<string> result;
	string s;
	void backtracking(const string& digits, int index)

2 确定终止条件

3 确定单层遍历逻辑

	int digit = digits[index] - '0'; // 将 index 指向的数字转为 int
	string letters = letterMap[digit]; // 取数字对应的字符集
	for (int i = 0; i < letters.size(); i++) {
	s.push_back(letters[i]); // 处理
	backtracking(digits, index + 1); // 递归，注意 index+1，一下层要处理下一个数字了
	s.pop_back(); // 回溯
	}

完整代码

	class Solution {
	private:
	const string letterMap[10] = {
	"", // 0
	"", // 1
	"abc", // 2
	"def", // 3
	"ghi", // 4
	"jkl", // 5
	"mno", // 6
	"pqrs", // 7
	"tuv", // 8
	"wxyz", // 9
	};
	public:
	vector<string> result;
	string s;
	void backtracking(const string& digits, int index) {
	if (index == digits.size()) {
	result.push_back(s);
	return;
	}
	int digit = digits[index] - '0'; // 将 index 指向的数字转为 int
	string letters = letterMap[digit]; // 取数字对应的字符集
	for (int i = 0; i < letters.size(); i++) {
	s.push_back(letters[i]); // 处理
	backtracking(digits, index + 1); // 递归，注意 index+1，一下层要处理下一个数字了
	s.pop_back(); // 回溯
	}
	}
	vector<string> letterCombinations(string digits) {
	s.clear();
	result.clear();
	if (digits.size() == 0) {
	return result;
	}
	backtracking(digits, 0);
	return result;
	}
	};

回溯