C++回溯算法详解

引言

回溯算法是一种通过深度优先搜索系统性地遍历问题解空间的算法。它的核心思想是"试错"：逐步构建候选解，当发现当前选择无法得到有效解时，立即回退到上一步（这就是"回溯"的由来），尝试其他可能性。本文将通过算法题实战来逐渐讲解回溯算法的原理，使用方法。

2025.4.21

第一题

17. 电话号码的字母组合

1.1 题目解析

从上面的图片中可以看到，题目给出了一个指针数组[1,2,3,4,5,6,7,8,9]，希望我们把使用到的数组内容全部组合在一起，形成一个新的数组。如示例1中，使用了指针[2,3]，希望题目把数组[2,3]中的所有内容组合成一个新的数组，也就是[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]。

1.2 解题思路

回溯解法

从上面的题目解析中，我们可以知道题目考察的是：“如何设计一套逻辑，能让程序自己循环组合两个数组的内容。”

这就设计本篇文章的重点：回溯算法。回溯算法设计到两个知识：递归和循环。

想要彻底理解回溯算法，我们可以先抛弃递归的过程，单纯以循环的逻辑思考问题。

• 假设输入是2，只有一个字符，那么应该怎么解呢？ 按照题目要求2=“abc"，所以结果应该是[“a”,“b”,“c”]， 先不用想着怎么去写递归，只思考下怎么打印出这个结果。 这个太简单了，一个循环就搞定了：

vector<string> v1;
for(i=0;i<2("abc");i++) {
    tmp = i;
    v1.push_back(tmp);
}
return v1;

• 上面是伪代码，一个循环就搞定了。如果输入的是23，应该怎么做呢？23的结果是 [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] ，我们仍然不考虑怎么去写递归，只是考虑怎么把这个结果给弄出来。代码如下：

vector<string> v1;
for(i=0;i<2("abc");i++) {
    for(j=0;j<3("def");j++)
        tmp = i+j;
        v1.push_back(tmp);
}
return v1;

• 也就是说23这样的长度为2的字符串可以用两层循环搞定。如果输入的是234呢，仍然不要考虑怎么去写递归，而是想怎么把结果打印出来。

vector<string> v1;
for(i=0;i<2("abc");i+=1) {
    for(j=0;j<3("def");j+=1) {
        for(k=0;k<4("ghi");k+=1) {
            tmp = i+j+k;
            v1.push_back(tmp);
        }
    }
}
return v1;

• 这次用了三层循环。如果输入的是2345，那么代码可以这么写：

vector<string> v1;
for(i=0;i<len("abc");i+=1) {
    for(j=0;j<len("def");j+=1) {
        for(k=0;k<len("ghi");k+=1) {
            for(n=0;n<len("jkl");n+=1)
                tmp = i+j+k+n;
                v1.push_back(tmp);
        }
    }
}
return v1;

• 这次是用了四层循环。现在是不是能看出一些门道了？对的。循环的嵌套层数，就是输入的字符串长度。输入的字符串长度是1，循环只有1层。输入的字符串长度是3，循环就是3层。如果输入的字符串长度是10，那么循环就是10层。可是输入的字符串长度是不固定的，对应的循环的嵌套层数也是不固定的，那这种情况怎么解决呢？这时候递归就派上用场了。
  
• 对于打印"2345"这样的字符串：
• 第一次递归就是上图中最下面的方格，然后处理完第一个字符2之后，将输入的字符改变成"345"并调用第二个递归函数。
• 第二次递归处理3，将字符串改变成"45"后再次递归。
• 第三次递归处理4，将字符串改变成"5"后继续递归。
• 第四次递归处理5，将字符串改变成""后继续递归。
• 最后发现字符串为空了，将结果放到列表中并返回。
• 上面是从函数调用的角度去看的，而每次调用下一层递归时，都需要将本层的一些处理结果放到一个临时变量中，再传递给下一层，从这个变量层层传递的变化看，就像一棵树一样，这个算法的时间复杂度很高，是O(3^n)这个级别的，空间复杂度是O(n)。
  

队列解法

• 我们可以利用队列的先进先出特点，再配合循环完成题目要求。我们先将2对应的字符"a",“b”,"c"依次放入队列中。
  

• 之后再从队列中拿出第一个元素"a"，跟3对应的字符"d",“e”,"f"挨个拼接。

• 于是队列就变成了下面这个样子：

• 按照同样的方式，再将"b"从队列中拿出，再跟3对应的字符"d",“e”,"f"挨个拼接，队列又变成下面这个样子：
  

1.3 解题代码

回溯解法

class Solution {
public:
    vector<string> ans; // 设为全局变量，方便helper函数引用
    vector<string> sList={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //字符表，注意不能用括号声明
    
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return {};  // 特判。如果字符串的长度为0，那么就停止打印。
        helper(digits, {}, 0);
        return ans;
    }

    // digits是字符串，idx是当前扫描到的字符串长度，s是字符串对应的字母
    void helper(string digits, string s, int idx){
        if(idx==digits.size()){ // 回溯条件，保证digits全部被扫描。
            ans.push_back(s);   // 将一种结果压入ans
            return;
        }
        else{
            // 依据digits的位数进行迭代，例如digits="234"
            // 第一层迭代为"2"，将遍历对应的字符串"abc"并更新字符串，依次为"a","b","c"
            // 第二层迭代为"3"，将遍历对应的字符串"def"并更新字符串，若上一层迭代为"a"，则添加、更新为"ad", "ae"与"af".
            int pos=digits[idx]-'0';  // 获取idx在digits的字符,如“2”对应的2
            string tmpStr=sList[pos];  // 获取下标pos对应的字符串，如2对应的"abc"
            for(int i=0;i<tmpStr.size();i++){
                helper(digits,s+tmpStr[i],idx+1);   // 进行下一层迭代，注意同一层迭代时不改变s和idx等参数值
            }
        }
    }
};

队列解法

class Solution {
public:
    vector<string> ans;
    vector<string> sList={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //字符表
    
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return {};  
        queue<string> q;
        for(int i=0;i<digits.size();i++){  // 遍历digits
            int pos=digits[i]-'0'; // 数字
            string s=sList[pos]; // 数字对应字符串
            if(i==0){
                string initStr;
                for(int j=0;j<s.size();j++){
                    initStr=s[j];
                    q.push(initStr); // 填入单字符
                }
            }
            else{
                string fr=q.front();    // 队列首位
                while(fr.size()<i+1){   // 队列首位的字符串是否小于遍历digits的子串的长度
                    q.pop();            // 删除首位
                    for(int j=0;j<s.size();j++){
                        q.push(fr+s[j]);
                    }
                    fr=q.front();       // 更新队列首位
                }
            }
        }
        while(!q.empty()){
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};

以上内容均出自本篇文章。
链接：本篇文章的思路出处