LeetCode-题目详解（十一）：回溯算法【递归回溯、迭代回溯】【DFS是一个劲往某一个方向搜索；回溯算法建立在DFS基础之上，在搜索过程中，达到结束/裁剪条件后，恢复状态，回溯上一层，再次搜索】

我不是女神ヾ 2023-10-03 08:01 4阅读 0赞

#### 这里写目录标题 ####

*  一、概述
 *   *  1、深度优先遍历（DFS） 和回溯算法区别
     *  2、 何时使用回溯算法
     *  3、回溯算法步骤
     *  4、回溯问题的类型
 *  二、LeetCode案例
 *   *  39. 组合总和
     *  40. 组合总和II
     *  77. 组合
     *  216. 组合总和 III
     *  46. 全排列
     *  47. 全排列 II
     *  剑指 Offer 38. 字符串的排列
     *  剑指 Offer II 079. 所有子集
     *  90. 子集 II
     *  剑指 Offer II 085. 生成匹配的括号【22. 括号生成】
     *  剑指 Offer II 086. 分割回文子字符串【131. 分割回文串】
     *  79. 单词搜索【剑指 Offer 12. 矩阵中的路径】
     *  面试题13. 机器人的运动范围
     *  面试题 08.10. 颜色填充

## 一、概述 ##

### 1、深度优先遍历（DFS） 和回溯算法区别 ###

DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

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

回溯法是一种算法思想，而递归是一种编程方法，回溯法可以用递归来实现。

回溯法的整体思路是：搜索每一条路，每次回溯是对具体的一条路径而言的。对当前搜索路径下的的未探索区域进行搜索，则可能有两种情况：

*  当前未搜索区域满足结束条件，则保存当前路径并退出当前搜索；
 *  当前未搜索区域需要继续搜索，则遍历当前所有可能的选择：如果该选择符合要求，则把当前选择加入当前的搜索路径中，并继续搜索新的未探索区域。

上面说的未搜索区域是指搜索某条路径时的未搜索区域，并不是全局的未搜索区域。

回溯法搜所有可行解的模板一般是这样的：

res = []
    path = []
    
    def backtrack(未探索区域, res, path):
        if 未探索区域满足结束条件:
            res.add(path) # 深度拷贝
            return
        for 选择 in 未探索区域当前可能的选择:
            if 当前选择符合要求:
                path.add(当前选择)
                backtrack(新的未探索区域, res, path)
                path.pop()

### 2、 何时使用回溯算法 ###

当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

### 3、回溯算法步骤 ###

1.  画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
2.  根据题意，确立结束条件
3.  找准选择列表(与函数参数相关),与第一步紧密关联※
4.  判断是否需要剪枝
5.  作出选择，递归调用，进入下一层
6.  撤销选择

### 4、回溯问题的类型 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]  
注意：子集、组合与排列是不同性质的概念。子集、组合是无关顺序的，而排列是和元素顺序有关的，如 \[1，2\] 和 \[2，1\] 是同一个组合(子集)，但 \[1,2\] 和 \[2,1\] 是两种不一样的排列！！！！因此被分为两类问题

## 二、LeetCode案例 ##

### 39. 组合总和 ###

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

*  所有数字（包括 target）都是正整数。
 *  解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
    所求解集为：
    [
      [7],
      [2,2,3]
    ]

示例 2：

输入：candidates = [2,3,5], target = 8,
    所求解集为：
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

提示：

*  1 <= candidates.length <= 30
 *  1 <= candidates\[i\] <= 200
 *  candidate 中的每个元素都是独一无二的。
 *  1 <= target <= 500

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

思路分析：根据示例 1：输入: candidates = \[2, 3, 6, 7\]，target = 7。

*  候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；
 *  同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。

基于以上的想法，可以画出如下的树形图。建议大家自己在纸上画出这棵树，这一类问题都需要先画出树形图，然后编码实现。

编码通过 深度优先遍历 实现，使用一个列表，在 深度优先遍历 变化的过程中，遍历所有可能的列表并判断当前列表是否符合题目的要求，成为「回溯算法」（个人理解，非形式化定义）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]

*  以 target = 7 为 根结点 ，创建一个分支的时 做减法 ；
 *  每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
 *  减到 00 或者负数的时候停止，即：结点 00 和负数结点成为叶子结点；
 *  所有从根结点到结点 00 的路径（只能从上往下，没有回路）就是题目要找的一个结果。

这棵树有 44 个叶子结点的值 00，对应的路径列表是 \[\[2, 2, 3\], \[2, 3, 2\], \[3, 2, 2\], \[7\]\]，而示例中给出的输出只有 \[\[7\], \[2, 2, 3\]\]。即：题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。

产生重复的原因是：在每一个结点，做减法，展开分支的时候，由于题目中说 每一个元素可以重复使用，我们考虑了 所有的 候选数，因此出现了重复的列表。

一种简单的去重方案是借助哈希表的天然去重的功能，但实际操作一下，就会发现并没有那么容易。

可不可以在搜索的时候就去重呢？答案是可以的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要 按某种顺序搜索。具体的做法是：每一次搜索的时候设置 下一轮搜索的起点 begin，请看下图。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]  
即：从每一层的第 22 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。

如果题目要求，结果集不计算顺序，此时需要按顺序搜索，才能做到不重不漏。「力扣」第 47 题（ 全排列 II ）、「力扣」第 15 题（ 三数之和 ）也使用了类似的思想，使得结果集没有重复。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]

回溯算法模板【Python】：

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            self.result = []
            self.path = []
    
            self.back_tracking(candidates, target, 0, 0)
    
            return self.result
    
        def back_tracking(self, nums, target, total, start):
            if total > target:
                return
    
            if total == target:
                curr_path = self.path[:]    # 对于python来说，必不可少
                self.result.append(curr_path)
                return
            
            for i in range(start, len(nums)):
                self.path.append(nums[i])
                total += nums[i]
                self.back_tracking(nums, target, total, i)
                self.path.pop()
                total -= nums[i]

回溯算法模板【C++】：

class Solution {
       
        
    public:
        vector<vector<int>> result;
        vector<int> path;
    
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
       
        
            backTracking(candidates, target, 0, 0);
            return result;
        }
    
        void backTracking(vector<int>& nums, int target, int total, int start){
       
        
            if(total > target){
       
        
                return;
            }
            if(total == target){
       
        
                result.push_back(path);
                return;
            }
            for(int i = start; i < nums.size(); i++){
       
        
                path.push_back(nums[i]);
                total += nums[i];
                backTracking(nums, target, total, i);
                path.pop_back();
                total -= nums[i];
            }
        }
    };

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

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    
            result = []
    
            # 回溯算法
            def dfs(nums, temp_target, path):
    
                # 递归结束条件
                if temp_target < 0:
                    return
                
                # 逻辑主体部分
                if temp_target == 0:
                    result.append(path)
    
                # 递归
                for idx, num in enumerate(nums):
                    dfs(nums[idx:], temp_target - num, path + [num])
    
    
            dfs(candidates, target, [])
            
            return result

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            self.result = []
            self.dfs(candidates, target, [])
            return self.result
    
        def dfs(self, nums, target, path):
            if sum(path) > target:
                return
    
            if sum(path) == target:
                self.result.append(path)
                return
            
            for idx, num in enumerate(nums):
                self.dfs(nums[idx:], target, path + [num])

剪枝提速

*  根据上面画树形图的经验，如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的；
 *  排序是为了提高搜索速度，对于解决这个问题来说非必要。但是搜索问题一般复杂度较高，能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况，都试一下。

回溯算法模板【Python】：

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            self.result = []
            self.path = []
    
            candidates.sort()   # 排序不是必须操作
            self.back_tracking(candidates, target, 0, 0)
    
            return self.result
    
        def back_tracking(self, nums, target, total, start):
            if total > target:
                return
    
            if total == target:
                curr_path = self.path[:]    # 对于python来说，必不可少
                self.result.append(curr_path)
                return
            
            for i in range(start, len(nums)):
                self.path.append(nums[i])
                total += nums[i]
                self.back_tracking(nums, target, total, i)
                self.path.pop()
                total -= nums[i]

回溯算法模板【C++】：

class Solution {
       
        
    public:
        vector<vector<int>> result;
        vector<int> path;
    
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
       
        
            sort(candidates.begin(), candidates.end()); // 排序不是必须操作
            
            backTracking(candidates, target, 0, 0);
            return result;
        }
    
        void backTracking(vector<int>& nums, int target, int total, int start){
       
        
            if(total > target){
       
        
                return;
            }
            if(total == target){
       
        
                result.push_back(path);
                return;
            }
            for(int i = start; i < nums.size(); i++){
       
        
                path.push_back(nums[i]);
                total += nums[i];
                backTracking(nums, target, total, i);
                path.pop_back();
                total -= nums[i];
            }
        }
    };

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

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    
            result = []
    
            # 回溯算法
            def dfs(nums, temp_target, path):
    
                # 递归结束条件【剪枝：如果当前temp_target < 0，没必要枚举了，直接return】
                if temp_target < 0:
                    return
                
                # 逻辑主体部分
                if temp_target == 0:
                    result.append(path)
    
                # 递归
                for idx, num in enumerate(nums):
                    # 在搜索的时候就去重：这一类相同元素不计算顺序的问题，我们在搜索的时候就按某种顺序搜索。
                    # 从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
                    dfs(nums[idx:], temp_target - num, path + [num])
    
            candidates.sort()   # 排序不是必须操作
    
            dfs(candidates, target, [])
            
            return result

### 40. 组合总和II ###

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

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

说明：

*  所有数字（包括目标数）都是正整数。
 *  解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
    所求解集为:
    [
      [1,2,2],
      [5]
    ]

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

一句话题解：按顺序搜索，设置合理的变量，在搜索的过程中判断是否会出现重复集结果。

与第 39 题（组合之和）的差别：

*  第 39 题：candidates 中的数字可以无限制重复被选取；
 *  第 40 题：candidates 中的每个数字在每个组合中只能使用一次。

相同点是：相同数字列表的不同排列视为一个结果。

为了避免产生重复解，本题candidates务必排序。

如何去掉重复的集合（重点），为了使得解集不包含重复的组合。有以下 2 种方案：

*  使用 哈希表 天然的去重功能，但是编码相对复杂；
 *  这里我们使用和第 39 题和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]  
由第 39 题我们知道，数组 candidates 有序，也是 深度优先遍历 过程中实现「剪枝」的前提。

将数组先排序的思路来自于这个问题：去掉一个数组中重复的元素。很容易想到的方案是：先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。也就是说，剪枝发生在：同一层数值相同的结点第 2、3 … 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1 个结点的子集。

class Solution:
        def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
            self.result = []
            nums.sort() # 排序是必须操作
            self.dfs(nums, target, [])
            return self.result
        
        # 回溯算法
        def dfs(self, nums, target, path):
            # 递归结束条件【剪枝：如果当前total > target，没必要枚举了，直接return】
            if target < 0:
                return
            # 逻辑主体部分
            if target == 0:
                self.result.append(path)
            # 递归
            for idx, num in enumerate(nums):
                # 在搜索的时候就去重：这一类相同元素不计算顺序的问题，我们在搜索的时候就按某种顺序搜索。
                # 从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
                # 而且重复的元素要跳过，防止产生重复数组
                if idx > 0 and nums[idx] == nums[idx - 1]:
                    continue
                self.dfs(nums[idx + 1:], target - num, path + [num])

回溯算法模板【Python】：

class Solution:
        def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
            self.result = []
            self.path = []
            nums.sort() # 排序是必须操作
            self.back_tracking(nums, target, 0, 0)
            return self.result
        
        # 回溯算法
        def back_tracking(self, nums, target, total, start):
            # 递归结束条件【剪枝：如果当前total > target，没必要枚举了，直接return】
            if total > target:
                return
            # 逻辑主体部分
            if total == target:
                curr_path = self.path[:]    # 深拷贝
                self.result.append(curr_path)
            # 递归
            for i in range(start, len(nums)):
                # 在搜索的时候就去重：这一类相同元素不计算顺序的问题，我们在搜索的时候就按某种顺序搜索。
                # 从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
                # 而且重复的元素要跳过，防止产生重复数组
                if i > start and nums[i] == nums[i - 1]:
                    continue
                self.path.append(nums[i])
                total += nums[i]
                self.back_tracking(nums, target, total, i + 1)
                self.path.pop()
                total -= nums[i]

回溯算法模板【C++】：

class Solution {
       
        
    public:
        vector<vector<int>> result; // 存放组合集合
        vector<int> path;           // 符合条件的组合
    
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
       
        
            sort(candidates.begin(), candidates.end());
            backTracking(candidates, target, 0, 0);
            return result;
        }
    
        void backTracking(vector<int>& nums, int target, int total, int start){
       
        
            // 递归结束条件【剪枝：如果当前total < 0，没必要枚举了，直接return】
            if(total > target){
       
        
                return;
            }
    
            // 逻辑主体部分
            if(total == target){
       
        
                result.push_back(path);
            }
    
            // 递归
            for(int i = start; i < nums.size(); i++){
       
        
                // 要对同一树层使用过的元素进行跳过
                if(i > start && nums[i] == nums[i - 1]){
       
        
                    continue;
                }
    
                //记忆【将当前元素加入到path中】
                path.push_back(nums[i]);
                total += nums[i];
    
                backTracking(nums, target, total, i + 1);
    
                // 回溯【将当前元素从path删除】
                path.pop_back();
                total -= nums[i];
            }
        }
    };

class Solution {
       
        
    public:
        vector<vector<int>> result; // 存放组合集合
        vector<int> path;           // 符合条件的组合
    
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
       
        
            sort(candidates.begin(), candidates.end());
            backTracking(candidates, target, 0, 0);
            return result;
        }
    
        void backTracking(vector<int>& nums, int target, int total, int start){
       
        
            // 递归结束条件【剪枝：如果当前total < 0，没必要枚举了，直接return】
            if(total > target){
       
        
                return;
            }
    
            std::cout << "total = " << total << "; ";
            std::cout << "path = [";
            for(auto num: path) {
       
        
                std::cout << num;
            }
            std::cout << "]" << std::endl;
    
            // 逻辑主体部分
            if(total == target){
       
        
                result.push_back(path);
            }
    
            // 递归
            for(int i = start; i < nums.size(); i++){
       
        
                // 要对同一树层使用过的元素进行跳过
                if(i > start && nums[i] == nums[i - 1]){

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210615112750200.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210614225015102.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210614224029917.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210614224212267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210615113733283.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2021061422552991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210614225737541.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center