ii 组合总和_【数据结构】Leetcode——回溯算法：组合/分割问题

傷城~ 2023-01-04 11:56 155阅读 0赞

我相信苦涩的眼泪

![af9329059fd35b4b96b0074d8e8cd97b.png][]

--------------------

**开始之前学习一个单词热热身：** **non-negligible** **adj. 不可忽视的；重大的;**

--------------------

### Contents ###

*  "组合问题"，即\`N\`个数里面按一定规律找出\`k\`个数的集合。
    
     *  1 组合(77)
     *  2 组合总和 III(216)
     *  3 电话号码的字母组合(17)
     *  4 组合总和(39，集合无重复元素、数字可重复选取)
     *  5 组合总和 II(40，集合有重复元素、数字不可重复选取)
 *  "分割问题"，即一个字符串按一定规则有几种切割方式。
    
     *  6 分割回文串(131)
     *  7 复原IP地址(93)
     *  8 子集(78)
     *  9 求根到叶子节点数字之和(129)

--------------------

**回溯法解决的问题都可以抽象为树形结构(N叉树)，回溯法的搜索过程就是一个树形结构的遍历过程。** **回溯法的求解过程可表示为在一棵解空间树做深度优先搜索。**  **按照回溯算法模板做题，最起码你对照问题知道该思考什么东西。。**

![b40e46f747008348cd854cce779fb747.png][]

--------------------

"组合问题"，即 `N`个数里面按一定规律找出 `k`个数的集合。

## 1 组合(77) ##

**题目：**

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

**示例：**

![bf66dbb65521b8868cb65ff3ad1d5f97.png][]

**思路：**(图片来源：代码随想录)![26e3ea7968db91933e190c99469f2890.png][]     本题符合"组合问题"，即 `N`个数里面按一定规律找出 `k`个数的集合。按照回溯算法模板框架：

① 终止条件

题目需返回 `k`个数的集合，则当存储子集的 `size`等于 `k`时，达到终止条件，应该返回；

② 单层搜索过程      如图中， `for`循环用于横向遍历，递归用于纵向遍历；定义一个参数 `startIndex`用于记录横向遍历中从哪一个数开始。

③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，参数为 `n、k、startIndex`。

class Solution {
         public:        vector<vector <int>> res;        vector<int> temp;    void backtracking(int n, int k, int startIndex){
                 if(temp.size()==k){
                     res.push_back(temp);            return;        }        for(int i=startIndex; i<=n; i++){
                     temp.push_back(i);  //相当于记录for循环之下的第一个path            backtracking(n, k, i+1);            temp.pop_back();  //相当于模板中的回溯,撤销处理结果        }    }    vector<vector<int>> combine(int n, int k) {
                 backtracking(n, k, 1);        return res;    }};

可以对如上算法进行剪枝优化，如下图每一个矩形代表本层的一个循环，当每个循环开始的起点之后的数字个数小于所需要的数字个数的话，该循环是无意义的。所以可以在递归中每一层的 `for`循环所选择的起始位置进行剪枝。(图片来源：代码随想录) ![25e6399d52be9f803bcb593e40d3af0a.png][]     可以修改上述代码中的 `for`循环条件中的i的选择范围。

for(int i=startIndex; i<=n; i++){

已经选择元素个数为 `temp.size()`，还需选择 `k-temp.size()`个元素个数，在集合n中至少需要从 `n-(k-temp.size())+1`处开始遍历。故可以将 `for`循环条件修改为

for(int i=startIndex; i<=n-(k-temp.size())+1; i++){

剪枝后的结果再leetcode中的执行用时由 `44ms`提升为 `16ms`。

--------------------

## 2 组合总和 III(216) ##

**题目：**     找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 **示例：** ![891e69c5e00c5e2db3738df912f35334.png][] **思路：**按照回溯算法模板框架：① 终止条件      题目需返回 `k`个数的集合，则当存储子集的 `size`等于 `k`时，达到终止条件，应该返回；② 单层搜索过程      如图中， `for`循环用于横向遍历，递归用于纵向遍历；定义一个参数 `startIndex`用于记录横向遍历中从哪一个数开始。因为组合中只含有1-9的正整数，故单层 `for`循环限制条件为 `i<=9`；在将 `i`加入到路径组合 `path`过程的同时将 `targetSum=targetSum-i;`，以便修改纵向遍历递归的剩余求和值。③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，参数为求和值 `targetSum`、求和个数 `k`和横向遍历起始位置 `startIndex`。

class Solution {
         public:    vector> combinationSum3(int k, int n) {
                 backtracking(n, k, 1);        return res;    }private:    vector> res;    vector path;    void backtracking(int targetSum, int k, int startIndex){
                 if(path.size()==k){
                     if(targetSum==0) res.push_back(path);            return;        }        for(int i=startIndex; i<=9; i++){ // 处理过程和回溯过程是一一对应的，处理中加、减掉的东西，在回溯时要补回来！            targetSum = targetSum-i; //处理            path.push_back(i);  //处理            backtracking(targetSum, k, i+1);            targetSum = targetSum+i; //回溯            path.pop_back();  //回溯        }    }};

--------------------

## 3 电话号码的字母组合(17) ##

**题目：**     给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。     给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 ![71cb0a8558935405122b92ef2b6d2219.png][] **示例：** ![bb8913e9d55954da88f65e7767a5fe79.png][] **思路：**     想一个简单的例子，输入为"23"，只要对2和3代表的字母进行双重循环遍历就好；那么如果输出为"234"，则需要进行三重循环遍历……这种 `for`循环次数与输入长度有关的问题均需要采用回溯算法。在确定使用回溯算法后，对照回溯算法模板思考它的模板框架：① 终止条件     输入数字字符串的长度即为转换为每个字母字符串的长度，所以当存储的字母字符串长度等于输入字符串长度时达到终止条件；② 单层搜索过程      在单层搜索过程中，首先获得输入数字字符串中的一位数字，其次在存有数字与字母对应关系的 `map`中查询该数字对应的字母串；该字母串的长度即为该层横向遍历的宽度；纵向遍历的高度等于输入数字字符串的长度；③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，参数为数字字符串 `digits`和数字字符串的索引 `index`。

class Solution {
         public:    vector res;    string temp;    map table = {
                 {2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}    };    void backtracking(const string &digits, int index){
                 if(index==digits.size()){
                     res.push_back(temp);            return;        }        int n = digits[index] - '0';        string s1 = table[n];        for(int i=0; i            temp.push_back(s1[i]);            backtracking(digits, index+1);            temp.pop_back();        }        return;    }    vector letterCombinations(string digits) {
                 if(digits.size()==0) return res;        backtracking(digits, 0);        return res;    }};

--------------------

## 4 组合总和(39，集合无重复元素、数字可重复选取) ##

**题目：**     给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。     candidates 中的数字可以无限制重复被选取。 **示例：** ![86a9fabca2ee353dec3342b0a2c9fc58.png][] **思路：**按照回溯算法模板框架：① 终止条件      利用 `target`不断减去遍历到的数字，若 `target`恰好为0，则达到终止条件，应该保存该子集并返回；② 单层搜索过程      如图中， `for`循环用于横向遍历，递归用于纵向遍历；定义一个参数 `startIndex`用于记录横向遍历中从哪一个数开始。每一层循环过程中，进行 `target=target-candidates[i];`操作，不要忘记在回溯时要进行 `target=target+candidates[i];`操作。③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，参数为 `candidates、target、startIndex`。 **添加剪枝优化：**     可以首先对给定数组进行排序，然后在横向遍历过程中(即对于for循环中的判断条件)，如果 `target-candidates[i]<=0`,则说明之后的数字不能使得 `target`为0，故剪枝掉。 **尤其注意这样剪枝的前提是给定的数组是升序的。**

class Solution {
         public:    vector path;    vector> res;    void backtracking(vector& candidates, int target, int startIndex){
                 if(target==0){
                     res.push_back(path);            return;        }        for(int i=startIndex; i=0; i++){
                     path.push_back(candidates[i]);            target = target - candidates[i];            backtracking(candidates, target, i);            target = target + candidates[i];            path.pop_back();        }    }    vector> combinationSum(vector& candidates, int target) {
                 if(candidates.size()==0) return {};        sort(candidates.begin(), candidates.end());//剪枝的必要前提        backtracking(candidates, target, 0);        return res;    }};

--------------------

## 5 组合总和 II(40，集合有重复元素、数字不可重复选取) ##

**题目：**     给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。     candidates 中的每个数字在每个组合中只能使用一次。 **示例：** ![091b84177c16ee54af231f2359fab9d2.png][] **思路：**     集合中有重复元素，如果按前几道题的思路，选定一个元素后再去找 `target-candidates[i];`，最后结果中会出现重复子集，本题的关键是如何 **去重**。去重的终极目标是：返回答案的子集中可以包含重复元素(因为给定集合中包含重复元素)而不可以包含相同的子集。     举一个简单的例子：(来自代码随想录) ![ee48ee715c72fa373a90e37e0bc28f1c.png][] **故去重去掉的是同一树层上"使用过"的元素。**

"使用过"的元素通过引入一个布尔型的used数组来标识，按照回溯算法模板框架：

① 终止条件      与39题相同，利用 `target`不断减去遍历到的数字，若 `target`恰好为0，则达到终止条件，应该保存该子集并返回；② 单层搜索过程       `for`循环用于横向遍历，递归用于纵向遍历；定义一个参数 `startIndex`用于记录横向遍历中从哪一个数开始。 ![cf54fadcbf9cec3a392bf48bc0863c8a.png][]     如上图，如果

candidates[i]==candidates[i-1]&&used[i-1]==false

说明同一树层使用过 `candidates[i-1]`，则此时 `for`循环应执行 `continue`操作。

// used[i - 1] == true，说明同一树支candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过

③ 确定回溯函数的返回值及参数      返回值一般为 `void`，参数为 `candidates、target、startIndex、used`。 **注意：别忘了对给定数组进行升序排序！！**

class Solution {
         private:    vector path;    vector> res;    void backtracking(vector& candidates, int target, int startIndex, vector& used){
                 if(target==0){
                     res.push_back(path);            return;        }        for(int i=startIndex; i=0; i++){
                     if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false){
                         continue;            }            path.push_back(candidates[i]);            target = target-candidates[i];            used[i]=true;            backtracking(candidates, target, i+1, used);            //开始回溯            used[i]=false;            target = target+candidates[i];            path.pop_back();        }    }public:    vector> combinationSum2(vector& candidates, int target) {
                 vector used(candidates.size(), false);        sort(candidates.begin(), candidates.end());        backtracking(candidates, target, 0, used);        return res;    }};

--------------------

# **"分割问题"，即一个字符串按一定规则有几种切割方式。** #

## 6 分割回文串(131) ##

**题目：**     给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 **示例：** ![d66313312aea02f074ae2bf16b457780.png][] **思路：**1、切割问题类似组合问题，切割问题也可抽象为一棵树形结构； ![cb79088202b89c4fe8045ba260105688.png][]2、按照回溯算法模板框架：① 终止条件      上图中的每一根红线即表示一个切割位置，在切割到字符串末尾时达到终止条件，应返回；在代码中用 `startIndex`代表切割线，当 `startIndex>=s.size()`时，表示已切割到字符串末尾；② 单层搜索过程      在 `for`循环中，区间 `[startIndex,i]`就是截取的字符串，首先判断截取的字符串是否是回文字符串，若是则存入 `path`中，否则直接跳过。③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，参数为 `s、startIndex`。3、判断回文字符串      使用双指针法循环判断回文字符串即可。

class Solution {
         private:    vector path;    vector> res;    void backtracking(string& s, int startIndex){
                 if(startIndex>=s.size()){
                     res.push_back(path);            return;        }        for(int i=startIndex; i            if(isPalindrome(s, startIndex, i)){
                         string str = s.substr(startIndex, i-startIndex+1);                path.push_back(str);            }            else{
                         continue;            }            backtracking(s, i+1);            path.pop_back();        }    }    bool isPalindrome(const string& s, int start, int end){
                 for(int i=start, j=end; i            if(s[i]!=s[j]) return false;        }        return true;    }public:    vector> partition(string s) {
                 backtracking(s, 0);        return res;    }};

**本题的几个难点：**

*  切割问题可抽象为组合问题；
 *  如何模拟切割线；
 *  切割问题中递归如何终止；
 *  在递归循环中如何截取子串
    
        stringstr=s.substr(startIndex,i-startIndex+1);
 *  如何判断回文

--------------------

## 7 复原IP地址(93) ##

**题目：**     给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。     有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成，且不能含有前导 0)，整数之间用 '.' 分隔。 **示例：** ![b90068f50daeebe81ebd0248fca24feb.png][] **思路：**     本题与分割回文串(131)题类似，同样都是分割问题。1、判断子串是否合法主要考虑到如下三点：

*  段位以0为开头的数字不合法
 *  段位里有非正整数字符不合法
 *  段位如果大于255了不合法

2、按照回溯算法模板框架：① 终止条件      当记录有三个'.'且最后一段子串是有效子串时，存入答案容器并返回；② 单层搜索过程      在 `for`循环中，区间 `[startIndex,i]`是截取的字符串，首先判断截取的字符串是否有效，若有效则在其有效子串后添加'.'，注意若添加了'.'后，下次回溯的起始位置应为 `i+2`('.'占据了一个位置)，否则直接跳过。③ 确定回溯函数的返回值及参数      回溯函数的返回值一般为 `void`，因为仅分割给定字符串一次，故回溯函数需要变量 `startIndex`来记录下一层分割的起始位置，本题还需一个用于记录'.'的数量的变量 `pointnum`，回溯函数参数为 `s、startIndex、pointnum`。3、剪枝       `IP`地址最多不可超过12位数字，故在for循环中加入剪枝条件即可。

class Solution {
         private:    vector res;    void backtracking(string& s, int startIndex, int pointnum){
                 if(pointnum==3 && isValid(s, startIndex, s.size()-1)) { // 逗点数量为3时分隔结束，判断第四段子字符串是否合法，如果合法则存入res中            res.push_back(s);            return;        }        for(int i=startIndex; i            if(isValid(s, startIndex, i)){
                         s.insert(s.begin()+i+1, '.');                pointnum++;                backtracking(s, i+2, pointnum);                pointnum--;                s.erase(s.begin()+i+1);            }            else break;        }    }    bool isValid(const string& s, int start, int end){
                 if(start>end) return false;        if(s[start]=='0'&&start!=end) return false;        int num=0;        for(int i=start; i<=end; i++){
                     if(s[i]>'9' || s[i]                return false;            }            num = num*10+(s[i]-'0');            if(num>255) return false;        }        return true;    }public:    vector restoreIpAddresses(string s) {
                 res.clear();        backtracking(s, 0, 0);        return res;    }};

--------------------

## 8 子集(78) ##

**题目：**     给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集(幂集)。 **示例：** ![7dd2a477c5ca4cb4e4947ba046116a4a.png][] **思路：**     之前的组合问题和分割问题是收集数的叶子结点，而子集问题是收集树的所有节点。在一个集合中，取过的元素不会再取，所以需要 `startIndex`变量。经过前8道题的练习，本题即为一道标准的模板题，较为简单。

class Solution {
         private:    vector path;    vector> res;    void backtracking(vector& nums, int startIndex){
                 res.push_back(path);        if(startIndex>=nums.size()) return;//z回溯终止条件可以不加，因为for循环中i不会超过nums.size()        for(int i=startIndex; i            path.push_back(nums[i]);            backtracking(nums, i+1);            path.pop_back();        }    }public:    vector> subsets(vector& nums) {
                 backtracking(nums, 0);        return res;    }   };

--------------------

## 9 求根到叶子节点数字之和(129) ##

**题目：**     给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。计算从根到叶子节点生成的所有数字之和。 **示例：** ![60c716678ae97d07e58276ca8be6af8c.png][] **思路：**     本题将递归和回溯结合起来，首先深度遍历树将每一条从根节点到叶子结点的路径存入 `vector`中，接着将 `vector`的数转为 `int`值，最后将所有 `int`值求和即可。     在树的遍历中，递归终止条件为当遍历到叶子结点时停止递归；对于单层递归逻辑，将遍历到的节点值存入 `vector`中，并接着递归左/右子节点； **这里要注意回溯和递归要永远在一起，一个递归，对应一个回溯，是一对一的关系！**

class Solution {
         public:    int sumNumbers(TreeNode* root) {
                 if(!root) return 0;        path.push_back(root->val);        traversal(root);        return res;    }private:    vector path;    int res=0;    int vectorToInt(vector path){
                 int sum=0;        for(int i=0; i            sum = sum*10 +path[i];        }        return sum;    }    void traversal(TreeNode* root){
                 if(!root->left && !root->right){
                     res += vectorToInt(path);            return;        }        if(root->left){
                     path.push_back(root->left->val);            traversal(root->left);            path.pop_back();        }        if(root->right){
                     path.push_back(root->right->val);            traversal(root->right);            path.pop_back();        }    }};

--------------------

?往期分享

【数据结构】Leetcode——哈希表

【数据结构】Leetcode——二叉搜索树

【数据结构】Leetcode——遍历树 经典题

【数据结构】Leetcode——树 递归经典题

【数据结构】Leetcode—— 列表 / 链表

[af9329059fd35b4b96b0074d8e8cd97b.png]: /images/20221119/0c19e2c8001e43e680ac8ec921ccf615.png
[b40e46f747008348cd854cce779fb747.png]: /images/20221119/ed0f3a2607034c7f93152ee418cb4a24.png
[bf66dbb65521b8868cb65ff3ad1d5f97.png]: https://img-blog.csdnimg.cn/img_convert/bf66dbb65521b8868cb65ff3ad1d5f97.png
[26e3ea7968db91933e190c99469f2890.png]: https://img-blog.csdnimg.cn/img_convert/26e3ea7968db91933e190c99469f2890.png
[25e6399d52be9f803bcb593e40d3af0a.png]: https://img-blog.csdnimg.cn/img_convert/25e6399d52be9f803bcb593e40d3af0a.png
[891e69c5e00c5e2db3738df912f35334.png]: https://img-blog.csdnimg.cn/img_convert/891e69c5e00c5e2db3738df912f35334.png
[71cb0a8558935405122b92ef2b6d2219.png]: https://img-blog.csdnimg.cn/img_convert/71cb0a8558935405122b92ef2b6d2219.png
[bb8913e9d55954da88f65e7767a5fe79.png]: https://img-blog.csdnimg.cn/img_convert/bb8913e9d55954da88f65e7767a5fe79.png
[86a9fabca2ee353dec3342b0a2c9fc58.png]: https://img-blog.csdnimg.cn/img_convert/86a9fabca2ee353dec3342b0a2c9fc58.png
[091b84177c16ee54af231f2359fab9d2.png]: https://img-blog.csdnimg.cn/img_convert/091b84177c16ee54af231f2359fab9d2.png
[ee48ee715c72fa373a90e37e0bc28f1c.png]: https://img-blog.csdnimg.cn/img_convert/ee48ee715c72fa373a90e37e0bc28f1c.png
[cf54fadcbf9cec3a392bf48bc0863c8a.png]: https://img-blog.csdnimg.cn/img_convert/cf54fadcbf9cec3a392bf48bc0863c8a.png
[d66313312aea02f074ae2bf16b457780.png]: https://img-blog.csdnimg.cn/img_convert/d66313312aea02f074ae2bf16b457780.png
[cb79088202b89c4fe8045ba260105688.png]: https://img-blog.csdnimg.cn/img_convert/cb79088202b89c4fe8045ba260105688.png
[b90068f50daeebe81ebd0248fca24feb.png]: https://img-blog.csdnimg.cn/img_convert/b90068f50daeebe81ebd0248fca24feb.png
[7dd2a477c5ca4cb4e4947ba046116a4a.png]: https://img-blog.csdnimg.cn/img_convert/7dd2a477c5ca4cb4e4947ba046116a4a.png
[60c716678ae97d07e58276ca8be6af8c.png]: https://img-blog.csdnimg.cn/img_convert/60c716678ae97d07e58276ca8be6af8c.png