【回溯算法篇】组合问题

🌠作者：@阿亮joy.

🎆专栏：《数据结构与算法要啸着学》

🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

【回溯算法篇】组合问题

👉回溯算法👈

什么是回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。

许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称。回溯法主要解决的问题如下图：

【回溯算法篇】组合问题
注：组合是不强调元素顺序的，而排列是强调元素顺序的。比如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。记住组合无序，排列有序，就可以了。

回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解。如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

除了深度优先搜索，常用的还有广度优先搜索。

回溯算法的模板

回溯函数模板的返回值和参数

在回溯算法中，函数的名字一般是 BackTracking（原路返回）、DFS（深度优先遍历）或 BFS（广度优先遍历）。函数名字根据自己的习惯去，最好是顾名思义的。回溯算法的返回值一般是 void，参数一般是输出型参数。输出型参数在递归搜索的过程中，收集符合要求的结果，参数的多少一般取决于题目。

回溯函数的终止条件

回溯法解决的问题都可以抽象成树形结构，遍历树形结构是需要终止条件的。那回溯函数的终止条件是什么呢？树形结构的遍历是需要遍历到叶子节点，到了叶子节点就找到了符合要求的一个解了，然后就可以结束本层的递归。注：此处所指的叶子节点是符合题目要求的节点。遍历时也会遇到不符合结果的叶子节点，此这时候就需要回溯了，不再往下进行搜索。

回溯搜索的遍历过程

在上面我们提到了，回溯一般是在集合中搜索。集合的元素个数就构成了树的宽度，递归的深度就构成了树的深度。如下图所示：

【回溯算法篇】组合问题

注：for 循环可以理解是横向遍历，backtracking（递归）就是纵向遍历。

回溯算法模板伪代码

void backtracking(参数) 
{
    if (终止条件) 
    {
        收集结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小)) 
    {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

这份模板很重要，后面做回溯算法的题目就靠它了。

👉组合👈

【回溯算法篇】组合问题

组合问题是用回溯算法解决的经典题目。因为用回溯算法解决的问题都可以抽象为属性结构，那么我们就可以将组合问题抽象成下图的样子。

【回溯算法篇】组合问题

可以看出这棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不再重复取。第一次取1，集合变为2，3，4 。因为 k 为 2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合 [1,2] [1,3] [1,4]，以此类推。我们可以发现：n 就是树的宽度，k 就是递归的深度。

递归函数的参数：在这里，我们可以在类里声明两个私有变量来存储结果，分别是

vector<vector<int>> result

和

vector<int> path

。result 是用来存放符合条件结果的集合，而 path 是用来存放符合条件。函数里一定有两个参数，既然是集合 n 里面取 k 个数，那么 n 和 k 是两个 int 型的参数。为了防止出现重复的组合，还需要一个参数 startIndex 来记录下一层递归搜索的起始位置。

递归的终止条件：在前面我们提及到，到了叶子节点就可以收集结果了。那什么时候到达所谓的叶子结点呢？通过下图，我们可以发现：当 path 数组的元素个数到达了 k，就说明我们找到了子集大小为 k 的集合了，就可以收集结果了。注：path 是从根节点到叶子节点的路径。

【回溯算法篇】组合问题

单层的遍历搜索过程：回溯法的搜索过程就是树形结构的变量过程，for 循环用来横向遍历，递归用来纵向遍历。for 循环每次从 startIndex 开始，然后用 path 数组保存节点 i。

【回溯算法篇】组合问题

完整代码

class Solution 
{
private:
    vector<vector<int>> result;
    vector<int> path;

    void BackTracking(int n, int k, int startIndex)
    {
        if(path.size() == k)
        {
            // 收集结果
            result.push_back(path);
            return;
        }

        // 横向遍历
        for(size_t i = startIndex; i <= n; ++i)
        {
            path.push_back(i);  // 处理节点
            BackTracking(n, k, i + 1);  // 递归
            path.pop_back();    // 回溯
        }
    }

public:
    vector<vector<int>> combine(int n, int k) 
    {
        result.clear(); // 防止用同一个对象重复调用该函数,可以不做
        path.clear();   // 防止用同一个对象重复调用该函数,可以不做
        BackTracking(n, k, 1);
        return result;
    }
};

【回溯算法篇】组合问题

剪枝优化

我们知道，回溯是暴力搜索的过程，其实这个搜索的过程也是可以通过剪枝来优化一下的。

在横向遍历的过程中有如下代码：

for (int i = startIndex; i <= n; i++) 
{
    path.push_back(i);
    BackTracking(n, k, i + 1);
    path.pop_back();
}

这个遍历的范围是可以剪枝优化的，那怎么优化呢？来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。在第二层 for 循环，从元素 3 开始的遍历都没有意义了。

【回溯算法篇】组合问题

该题的剪枝优化是：如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。我们知道

path.size()

是已经选择的元素个数，

k - path.size()

是还需要的元素个数。for 循环是从 startIndex 开始的，也就是说从 startIndex 到循环的上界能够凑出

k - path.size()

个元素就能够得到符合要求的结果。如果不能凑出，就无法得到符合要求的结果，无需再遍历。那么现在我们就来求一下循环的上界是多少，求解过程如下图：

【回溯算法篇】组合问题

那么经过剪枝优化后，代码就变成下面的样子了。

class Solution 
{
private:
    vector<vector<int>> result;
    vector<int> path;

    void BackTracking(int n, int k, int startIndex)
    {
        if(path.size() == k)
        {
            // 收集结果
            result.push_back(path);
            return;
        }

        // 横向遍历                  // 剪枝优化
        for(size_t i = startIndex; i <= n + 1 - (k - path.size()); ++i) 
        {
            path.push_back(i);  // 处理节点
            BackTracking(n, k, i + 1);  // 递归
            path.pop_back();    // 回溯
        }
    }

public:
    vector<vector<int>> combine(int n, int k) 
    {
        result.clear(); // 防止用同一个对象重复调用该函数,可以不做
        path.clear();   // 防止用同一个对象重复调用该函数,可以不做
        BackTracking(n, k, 1);
        return result;
    }
};

【回溯算法篇】组合问题

👉组合总和 III👈

【回溯算法篇】组合问题

其实组合总和 III 的解题思路也和组合的思路是一样的。也是套用回溯算法的模板，就是修改一下递归终止的条件和 for 循环横向遍历是做到操作。

【回溯算法篇】组合问题

class Solution 
{
private:
    vector<vector<int>> result;
    vector<int> path;

    // tagetSum为目标和
    // k为要求每个组合中数字的个数
    // startIndex为下一层递归开始遍历的下标
    // sum为路径和
    void backtracking(int targetSum, int k, int startIndex, int sum)
    {
        if(path.size() == k)
        {
            if(sum == targetSum)
            {
                result.push_back(path); // 收集结果
            }
            return;
        }

        // 横向遍历
        for(int i = startIndex; i <= 9; ++i)
        {
            // 处理节点
            sum += i;
            path.push_back(i);
            // 递归,纵向遍历
            backtracking(targetSum, k, i + 1, sum);
            // 回溯
            sum -= i;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        result.clear(); // 可以不做
        path.clear();   // 可以不做
        backtracking(n, k, 1, 0);
        return result;
    }
};

注：startIndex 是为了防止重复选数的。

组合总和 III 的剪枝优化有两个地方可以优化，第一个是和组合的剪枝优化一下，就是已经选的元素个数加上剩余的元素个数无法到达 k；还有一个优化就是，如果 sum 已经大于 targetSum 了，就没必要再往下搜索了（尽管所需要元素个数没有达到 k 个）。这个优化当做递归的终止条件，也可以放在 for 横向遍历中。下方的代码是放在 for 的横向遍历中，注意剪枝之前需要把回溯做了。

class Solution 
{
private:
    vector<vector<int>> result;
    vector<int> path;

    // tagetSum为目标和
    // k为要求每个组合中数字的个数
    // startIndex为下一层递归开始遍历的下标
    // sum为路径和
    void backtracking(int targetSum, int k, int startIndex, int sum)
    {        
        if(path.size() == k)
        {
            if(sum == targetSum)
            {
                result.push_back(path);
            }
            return;
        }
                                    // 剪枝优化
        for(int i = startIndex; i <= 9 + 1 - (k - path.size()); ++i)
        {
            sum += i;
            path.push_back(i);
            if(sum > targetSum) // 剪枝优化
            {
                sum -= i;   // 剪枝之前先把回溯做了
                path.pop_back();    // 剪枝之前先把回溯做了
                return;
            }
            backtracking(targetSum, k, i + 1, sum);
            sum -= i;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        backtracking(n, k, 1, 0);
        return result;
    }
};

【回溯算法篇】组合问题

👉组合总和👈

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

【回溯算法篇】组合问题

组合总和这道题目是给定了候选数字的数组和目标和。那么 for 循环遍历的集合就变成了候选数字数组。因为可以选取重复的元素，那么下一层递归还是从 i 开始搜索。注：因为给出的数字集合有序的，所以可以先将其排序。

class Solution 
{
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(const vector<int>& candidates, int target, int sum, int startIndex)
    {
        // 收集结果
        if(sum == target)
        {
            result.push_back(path);
            return;
        }
                                                // 剪枝优化
        for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i)
        {
            // 各种可能
            path.push_back(candidates[i]);
            sum += candidates[i];
            //不用i+1了，表示可以重复读取当前的数
            backtracking(candidates, target, sum, i);
            // 回溯
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

【回溯算法篇】组合问题

👉组合总和 II👈

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

【回溯算法篇】组合问题

本题数组 candidates 的元素是有重复的，而组合总和是无重复元素的数组 candidates。本道题的难点就是数组 candidates 有重复的元素，但不能有重复的组合，所以我们要在搜索的过程中去掉重复的组合。

所以的去重，就是使用过的元素不能重复选取。因为组合问题可以抽象成树形结构，那么使用过在树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。那么问题来了，我们所要的结果是同一树枝上使用过的还是同一树层上使用过的。

看一下题目的输出结果，一个组合中是可以有相同元素的，但是两个组合是不能够相同的。那么我们要去重的就是同一树层上使用过的，同一树枝上的都是一个组合里的元素，不需要去重。那么我们需要加一个 bool 类型数组 used，用来记录同一树枝上的元素是否使用过。

【回溯算法篇】组合问题

当 candidates[i] == candidates[i - 1] 时，有以下两种情况：

used[i - 1] = true，说明同一树枝上 candidates[i - 1] 使用过
used[i - 1] = false，说明同一树层上 candidates[i - 1] 使用过

那为什么 used[i - 1] == false 就是同一树层呢？因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：

【回溯算法篇】组合问题

class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void BackTracking(const vector<int>& candidates, int target, int sum, int startIndex, vector<bool> used)
    {
        if(sum == target)
        {
            ret.push_back(path);
            return;
        }
                                            // 剪枝优化
        for(size_t i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i)
        {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
                continue;

            used[i] = true;
            path.push_back(candidates[i]);
            sum += candidates[i];
            // i+1表示一个数不能被重复选取
            BackTracking(candidates, target, sum, i + 1, used); 
            // 回溯
            used[i] = false;
            path.pop_back();
            sum -= candidates[i];
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        ret.clear();
        path.clear();
        size_t n = candidates.size();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        vector<bool> used(n, false);
        BackTracking(candidates, target, 0, 0, used); 
        return ret;
    }
};

【回溯算法篇】组合问题

注：这直接用 startIndex 来去重也是可以的，就不用used 数组了。

class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void BackTracking(const vector<int>& candidates, int target, int sum, int startIndex)
    {
        if(sum == target)
        {
            ret.push_back(path);
            return;
        }
                                            // 剪枝优化
        for(size_t i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i)
        {
            // 要对同一树层使用过的元素进行跳过
            if(i > startIndex && candidates[i] == candidates[i - 1])
                continue;

            path.push_back(candidates[i]);
            sum += candidates[i];
            // i+1表示一个数不能被重复选取
            BackTracking(candidates, target, sum, i + 1); 
            // 回溯
            path.pop_back();
            sum -= candidates[i];
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        ret.clear();
        path.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        BackTracking(candidates, target, 0, 0); 
        return ret;
    }
};

【回溯算法篇】组合问题

👉电话号码的字母组合👈

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

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

【回溯算法篇】组合问题

【回溯算法篇】组合问题

【回溯算法篇】组合问题

这道题是比较简单的，和上面的题的思路差不多，就不进行过多的讲解了，下面的代码有相应的注释。

class Solution 
{
private:
    // 数字和字符串之间的映射可以采用哈希表
    const string letterMap[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    vector<string> ret;
    string str;
    
    void BackTracking(const string& digits, int startIndex)
    {
        // 当下标和digits.size()是说明可以收集结果了
        if(startIndex == digits.size())
        {
            ret.push_back(str);
            return;
        }

        int digit = digits[startIndex] - '0';   // 将字符'1'指向的数字1
        string letters = letterMap[digit];  // 拿到数字对应的字符串

        for(size_t i = 0; i < letters.size(); ++i)
        {
            str.push_back(letters[i]);
            //递归,startIndex+1表明一下层要处理下一个数字了
            BackTracking(digits, startIndex + 1);  
            str.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) 
    {
        ret.clear();
        str.clear();
        if(digits.empty())
            return ret;
        BackTracking(digits, 0);
        return ret;
    }
};

【回溯算法篇】组合问题

class Solution {
private:
    // letterMap是数字到字母串的映射
    const string letterMap[10] = 
    {
        "",      // 0 
        "",      // 1
        "abc",   // 2
        "def",   // 3
        "ghi",   // 4
        "jkl",   // 5
        "mno",   // 6
        "pqrs",  // 7
        "tuv",   // 8
        "wxyz"   // 9
    };

    vector<string> result;

    // index为递归的深度，也为digits数字串的下标
    void backtracking(const string& digits, int index, const string& s)
    {
        // 收集结果
        if(index == digits.size())
        {
            result.push_back(s);
            return;
        }

        int digit = digits[index] - '0';
        string letters = letterMap[digit];  // letters是数字对应的字母串
        
        for(int i = 0; i < letters.size(); ++i)
        {
            backtracking(digits, index + 1, s + letters[i]);   // 回到上一层是还是s
        }
    }

public:
    vector<string> letterCombinations(string digits) 
    {
        if(digits.size() == 0)
        {
            return result;
        }

        backtracking(digits, 0, "");
        return result;
    }
};

【回溯算法篇】组合问题

👉总结👈

本篇博客主要讲解了什么是回溯算法、回溯算法主要解决的问题、回溯算法的模板、组合问题以及剪枝优化等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

【回溯算法篇】组合问题

目录

👉回溯算法👈

👉组合👈

👉组合总和 III👈

👉组合总和👈

👉组合总和 II👈

👉电话号码的字母组合👈

👉总结👈

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器