【数据结构与算法】带你玩透回溯法

柔光的暖阳◎ 2022-11-09 03:45 176阅读 0赞

看完你一定会有收获的，相信我!

### 文章目录 ###

*  回溯法
 *   *   *  算法模板
         *  回溯算法题的解题思路
         *  案例分析
         *   *  字母大小写全排列
             *  子集

# 回溯法 #

递归算法中非常经典的思想：回溯法。这样的算法思想通常都应用在一类问题上，这类问题叫做**树型问题**。

用回溯算法解决问题的一般步骤：

> 1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
> 
> 2 、确定易于搜索的解空间结构,使得能用`回溯法`方便地搜索整个解空间 。
> 
> 3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

简单来说，回溯法可以理解成为通过选择不同的岔路口，来寻找目的地，一个岔路口一个岔路口的去尝试找到目的地，如果走错了路的话，继续返回到上一个岔路口的另外一条路，直到找到目的地。

### 算法模板 ###

可以按照3个步骤来思考这类的问题：

1.  **「路径」**：记录做出的选择。
2.  **「选择列表/状态变量」**：通常而言，用数组存储可以选择的操作，或用状态变量记录当前操作位置。
3.  **「结束条件」**：一般而言，就是递归的结束点，也就是搜索的结束点。

result = []
    
    function backtrack(路径, 选择列表) { 
        if('满足结束条件') { 
            // 这里就是对答案做更新,依据实际题目出发
            result.push(路径)
            return
        } else { 
            for(let i = 0; i < 选择列表.length; i++) { 
                // 对一个选择列表做相应的选择
                
                做选择
                
                backtrack(路径, 选择列表)
                
                // 既然是回溯算法,那么在一次分岔路做完选择后
                // 需要回退我们之前做的操作
                
                撤销选择
            }
        }
    }

### 回溯算法题的解题思路 ###

使用刻意练习的方法训练回溯算法：

1、画出递归树，找到状态变量。即函数中的变量。

2、找出递归出口。

3、找出选择列表 / 表达式

4、进行剪枝操作

5、根据选择，递归调用。

6、撤销选择

### 案例分析 ###

#### [字母大小写全排列][Link 1] ####

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

> 输入：S = “a1b2”
> 
> 输出：\[“a1b2”, “a1B2”, “A1b2”, “A1B2”\]

> 输入：S = “3z4”
> 
> 输出：\[“3z4”, “3Z4”\]

> 输入：S = “12345”
> 
> 输出：\[“12345”\]

**解题思路：**

每个字母有状态，大写小写；对于数字，直接跳过。

*  遇到数字，没有产生新分支，直接往后搜索。
 *  遇到字母，需要搜索两次，1、大写 2、小写
 *  递归出口：搜索到最后，则加入结果数组中。我们需要维护一个Index，指向当前的字符。

**按照刻意练习的整理：**

1、递归树，状态变量：index 和 当前合成字符串。

![image-20210314142149172][]

2、递归出口：index === len

3、选择列表：数字直接往下搜索；字母则分大小写搜索两次

4、剪枝：暂时不需要

5、撤销操作：不用撤销。

#### [子集][Link 2] ####

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

> 输入: nums = \[1,2,3\]
> 
> 输出: \[ \[3\], \[1\], \[2\], \[1,2,3\], \[1,3\], \[2,3\], \[1,2\], \[\] \]

**解题思路：**

每个数字有两种状态，选与不选。我们可以从头进行搜素，记录状态变量index和当前新数组。

当index === len，递归结束，存入结果数组中。

对每个数字进行两次操作：

1、选择该数字，进行搜索。

2、不选择该数字，进行搜索。

注意需要在选择后，撤销操作。

**从刻意练习的思路捋一遍：**

1、递归树，状态变量，当前数字下标、当前新数组。

2、递归出口：index===len

3、选择列表：每个数字要或不要

*  要，数字存入新数组，进行搜索。
 *  不要，直接index+1搜索。

注意，选择数字后需要撤销操作。

4、剪枝：暂无。

5、撤销操作，pop

![image-20210314143259514][]

以下是我在网上看到一套不错的回溯算法题集，如果你还在刻意找的话，可以看看这里。

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>题目链接</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>子集，组合</td> 
   <td><a href="https://leetcode-cn.com/problems/subsets/" rel="nofollow">子集</a>、<a href="https://leetcode-cn.com/problems/subsets-ii/" rel="nofollow">子集 II</a>、<a href="https://leetcode-cn.com/problems/combinations/" rel="nofollow">组合</a>、<a href="https://leetcode-cn.com/problems/combination-sum/" rel="nofollow">组合总和</a>、<a href="https://leetcode-cn.com/problems/combination-sum-ii/" rel="nofollow">组合总和 II</a></td> 
  </tr> 
  <tr> 
   <td>全排列</td> 
   <td><a href="https://leetcode-cn.com/problems/permutations/" rel="nofollow">全排列</a>、<a href="https://leetcode-cn.com/problems/permutations-ii/" rel="nofollow">全排列 II</a>、<a href="https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/" rel="nofollow">字符串的全排列</a>、<a href="https://leetcode-cn.com/problems/letter-case-permutation/" rel="nofollow">字母大小写全排列</a></td> 
  </tr> 
  <tr> 
   <td>搜索</td> 
   <td><a href="https://leetcode-cn.com/problems/sudoku-solver/" rel="nofollow">解数独</a>、<a href="https://leetcode-cn.com/problems/word-search/" rel="nofollow">单词搜索</a>、<a href="https://leetcode-cn.com/problems/eight-queens-lcci/" rel="nofollow">N皇后</a>、<a href="https://leetcode-cn.com/problems/palindrome-partitioning/" rel="nofollow">分割回文串</a>、<a href="https://leetcode-cn.com/problems/binary-watch/" rel="nofollow">二进制手表</a></td> 
  </tr> 
 </tbody> 
</table>

附上每道题 使用刻意练习思路的题解：  
[子集2 题解][2]  
[组合 题解][Link 3]  
[组合总和 题解][Link 4]  
[组合总和2 题解][2 1]  
[全排列 题解][Link 5]  
[全排列2 题解][2 2]  
[字符串的全排列 题解][Link 6]  
[分割回文串 题解][Link 7]

[Link 1]: https://leetcode-cn.com/problems/letter-case-permutation/
[image-20210314142149172]: /images/20221023/210f6f87e95a4953a27b79a65f451d82.png
[Link 2]: https://leetcode-cn.com/problems/subsets/
[image-20210314143259514]: /images/20221023/a00fc09ecf49459a902c9d788381bc5d.png
[2]: https://blog.csdn.net/weixin_43786756/article/details/115108959?spm=1001.2014.3001.5501
[Link 3]: https://blog.csdn.net/weixin_43786756/article/details/115108942?spm=1001.2014.3001.5501
[Link 4]: https://blog.csdn.net/weixin_43786756/article/details/115108927?spm=1001.2014.3001.5501
[2 1]: https://blog.csdn.net/weixin_43786756/article/details/115108916?spm=1001.2014.3001.5501
[Link 5]: https://blog.csdn.net/weixin_43786756/article/details/115108904?spm=1001.2014.3001.5501
[2 2]: https://blog.csdn.net/weixin_43786756/article/details/115108896?spm=1001.2014.3001.5501
[Link 6]: https://blog.csdn.net/weixin_43786756/article/details/115108882?spm=1001.2014.3001.5501
[Link 7]: https://blog.csdn.net/weixin_43786756/article/details/115108866?spm=1001.2014.3001.5501