【C/C++练习】经典的排列组合问题（回溯算法）——电话号码的字母组合

📖题目描述

题目出处：电话号码的字母组合
示例：

📖题解
 这是一道典型的排列组合问题，根据输入，我们需要找到所有的组合。下面以输入字符串

digits = "23"

为例来讲解这道题目。
图解：

分析：
 首先要知道输入的字符串

"23"

中的数字字符分别对应哪些字符串，其中2对应字符串

"abc"

，3对应字符串

"def"

。接下来就该对这两个字符串中的字符进行排列组合，一共有

     3 
    
   
     × 
    
   
     3 
    
   
     = 
    
   
     9 
    
   
  
    3×3=9 
   
  
3×3=9种组合，答案很简单，难点在于如何有规律的选取出所有的结果，其实只需要把我们的选取过程转化成代码即可。选取过程如上图所示，**先要纵向去遍历**，一般这种也叫**DFS（深度优先遍历）**，接着**横向去遍历**，其中纵向遍历要在不同的集合中选取元素，需要借助**递归**来实现，横向遍历是针对一个集合的，所以可以借助for循环来实现。下面将结合代码来展示具体的选取过程。

建立映射关系：
 首先需要建立起

2-9

数字字符所对应的字符串，我们可以通过数组来实现，利用数组下标的对应关系，一个下标对应一个字符串，

2-9

就可以当作是数组的下标，但当前输入的是一个字符串，因此会涉及到将一个字符串中的数字字符转换成数字。

string arr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

开始选取：
 选取过程的代码需要考虑以下三个点：

• 确定递归函数所需的参数
• 递归的终止条件
• 单层遍历的逻辑

确定递归函数所需的参数：
 首先需要一个字符串

s

来收集每一次选取到的字符，当遇到终止条件，

s

收集到的所以字符九就是一个结果，我们要把这个结果存储起来，因此还需要一个字符串数组

res

来存储选取结果，其次我们需要知道当前要在哪个字符串中选取字符，为此还需要两个参数，一个是题目中的输入参数

digits

，只知道它是不够的，例如：通过

digits = "23"

我们只能知道要在

"abc"

和

"def"

两个字符串中选取，但是for循环是对一个字符串进行遍历，在一个字符串中选取，因此我们还需要传递一个参数来确定具体是在哪个字符串中选取。可以传一个size_t类型的

index

，用来表示

digits

字符串的下标，因为有了下标就可以唯一确定字符串中的一个数字字符，而一个数字字符就对应一个字符串。

voidCombinations(string s, vector<string>& res, string& digits, size_t index)

 注意，并没有把

s

设置成引用变量，这里的目的是，每收集到一个字符，加把他加到s字符串上，如果s是一个引用，s就始终表示同一块空间，那在找到一个结果，存储起来后，要把s重置才能进行下一个结果的查找。相反

res

是一个引用，因为可以把每次选出来的结果往同一块空间加，无需每次开空间，digits也同理，是否用引用要根据实际情况来定，不能一概而论。
递归的终止条件：
 递归结束，意味着选取出了一个结果，那递归的终止条件，就可以理解成，选取出一个结果的条件，还是以

digits = "23"

为例：选取出一个结果，即在

"abc"

和

"def"

两个字符串中各选取一个字符，此时出结果了，递归也应该结束了。如何知道在所有字符串中都选取了一个字符呢？还记得参数

index

嘛？它用来具体确定在哪个字符串中选组，这里只要在字符串

def

中选取之后，就可以得出一个结果，递归也就结束了。

if(index == digits.size())//此时说明已经在每个字符串中都选取了一个字符{
    res.push_back(s);//把结果存入结果集中return;}

单层遍历的逻辑：
 首先要知道知道当前遍历的是哪一个字符串，这需要通过第一步的映射关系得到，接着遍历得到一个字符后，把它加入到

s

中，然后通过递归，去下一个集合选取字符。

int i = digits[index]-'0';//把字符数字转换成普通数字
string str = arr[i];//根据映射关系找到，当前层要遍历的字符串for(size_t i =0; i < str.size(); i++)//遍历当前层的字符串{Combinations(s + str[i], res, digits, index +1);//获取到一个字符后，去下一个字符串获取下一个字符//s + str[i]：把戒指目前收集到的字符全传给下一层//res：结果集//index + 1：到下一个字符串中去获取字符}

完整代码展示：

classSolution{
    string arr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public:voidCombinations(string s, vector<string>& res, string& digits, size_t index){if(index == digits.size())//此时说明已经在每个字符串中都选取了一个字符{
            res.push_back(s);//把结果存入结果集中return;}int i = digits[index]-'0';
        string str = arr[i];for(size_t i =0; i < str.size(); i++){Combinations(s + str[i], res, digits, index +1);}}

    vector<string>letterCombinations(string digits){
        vector<string> res;//定义结果集if(digits.size()==0)//输入一个空串，直接返回{return res;}
        string str;Combinations("", res, digits,0);//""：表示目前什么结果也没收集到//0：从digits的第一个数组字符所对应的字符串开始搜索return res;}};

 今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是春人前进的动力！