给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
可以使用回溯法来解决这个问题。首先定义一个映射关系将数字与字母对应起来，然后使用回溯算法来生成所有可能的组合。
回溯算法是一种通过不断尝试各种可能性来解决问题的方法，通常用于求解组合、排列、子集等问题。它通过深度优先搜索的方式探索问题的所有解空间，并在搜索过程中进行剪枝，从而有效地找到满足特定条件的解。
下面是回溯算法的一般步骤：
选择路径： 从问题的初始状态出发，按照某种规则选择一个候选解的路径，即在问题的解空间中前进一步。
探索路径： 在当前选择的路径上继续向前探索，查找可能的解或部分解。
约束条件： 在探索过程中，判断当前路径是否满足问题的约束条件。如果不满足，则放弃该路径，回退到上一步，继续探索其他路径。
标记状态： 在进入下一层递归之前，通常需要修改问题的状态，以便记录当前路径的选择或处理过程。
回退路径： 当探索到底或者无法继续前进时，需要回退到上一层，撤销当前路径的选择，返回上一层继续探索其他路径。
结束条件： 当搜索到达问题的解空间的边界或者满足特定条件时，结束搜索，得到最终的解或者部分解。
回溯算法的核心思想是通过不断地选择、探索、回退和标记状态，逐步地搜索问题的解空间，直到找到所有满足条件的解或者确定无解。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 定义数字与字母的映射关系
vector<string> keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 回溯算法生成所有可能的组合
void backtrack(vector<string>& result, string& digits, string current, int index) {
// 如果当前组合的长度等于输入数字的长度，则将当前组合加入结果集
if (index == digits.length()) {
result.push_back(current);
return;
}
// 获取当前数字对应的字母集合
string letters = keypad[digits[index] - '0'];
// 遍历当前数字对应的每一个字母，进行回溯
for (char letter : letters) {
current.push_back(letter); // 添加当前字母到当前组合中
backtrack(result, digits, current, index + 1); // 递归处理下一个数字
current.pop_back(); // 回溯，撤销当前字母
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;
if (digits.empty()) return result; // 如果输入为空，则直接返回空结果集
string current = "";
backtrack(result, digits, current, 0); // 调用回溯算法生成所有可能的组合
return result;
}
int main() {
string digits = "23";
vector<string> combinations = letterCombinations(digits);
cout << "所有可能的字母组合：" << endl;
for (const string& combination : combinations) {
cout << combination << " ";
}
cout << endl;
return 0;
}
时间空间复杂度分析
假设输入数字串的长度为 ( n )，每个数字对应的字母集合的平均长度为 ( m )。
时间复杂度分析：
回溯算法：
对于每个数字，我们都需要尝试其对应的所有字母，这需要 ( O(m) ) 的时间。
由于有 ( n ) 个数字，因此总共的时间复杂度为 ( O(m^n) )。
结果集合生成：
生成结果集合的过程中，需要将所有可能的组合添加到结果集中，这也需要 ( O(m^n) ) 的时间。
综合起来，整个算法的时间复杂度为 ( O(m^n) )。
空间复杂度分析：
递归调用栈：
递归调用栈的深度最多为输入数字串的长度 ( n )，因此需要额外的 ( O(n) ) 的空间。
结果集合：
存储结果集合所需的空间取决于结果的数量。最坏情况下，结果数量为 ( O(m^n) )，因此需要 ( O(m^n) ) 的空间。
综合起来，整个算法的空间复杂度为 ( O(m^n) )。
总的来说，这个算法的时间和空间复杂度都是指数级别的，随着输入规模 ( n ) 和每个数字对应的字母集合的大小 ( m ) 的增加，其运行时间和所需空间将急剧增加。
