基础算法-递归与回溯思想&&解题思路&&解题模板(附经典例题)

矫情吗；* 2023-01-13 10:46 136阅读 0赞

### 文章目录 ###

*  思想
 *  解题模板总结
 *   *  1.什么时候用
     *  2.为什么这样用
     *  3.怎么用
 *  例题-全排列问题
 *   *  解题思路
     *  代码实现：
 *  例题-子集问题
 *   *  解题思路
     *  代码实现

# 思想 #

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

> 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 ——LeetCode

# 解题模板总结 #

## 1.什么时候用 ##

看两个特征：

1.  题目中暗示了一个或多个解，并且要求我们详尽地列举出每一个解的内容时，一定要想到 DFS、想到递归回溯。
2.  题目经分析后，可以转化为树形逻辑模型求解。

## 2.为什么这样用 ##

递归与回溯的过程，本身就是穷举的过程。题目中要求我们列举每一个解的内容，解从哪来？解是基于穷举思想、对搜索树进行恰当地剪枝后得来的。

这里需要大家注意到另一种问法：不问解的内容，只问解的个数。这类问题往往不用 DFS 来解，而是用动态规划.

## 3.怎么用 ##

一个模型——树形逻辑模型；两个要点——递归式和递归边界。  
树形逻辑模型的构建，关键在于找“坑位”，一个坑位就对应树中的一层，每一层的处理逻辑往往是一样的，这个逻辑就是递归式的内容。至于递归边界，要么在题目中约束得非常清楚、要么默认为“坑位”数量的边界。  
用伪代码总结一下编码形式，大部分的题解都符合以下特征：

function xxx(入参) {
      前期的变量定义、缓存等准备工作 
      
      // 定义路径栈
      const path = []
      
      // 进入 dfs
      dfs(起点) 
      
      // 定义 dfs
      dfs(递归参数) {
        if(到达了递归边界) {
          结合题意处理边界逻辑，往往和 path 内容有关
          return   
        }
        
        // 注意这里也可能不是 for，视题意决定
        for(遍历坑位的可选值) {
          path.push(当前选中值)
          处理坑位本身的相关逻辑
          path.pop()
        }
      }
    }

# 例题-全排列问题 #

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：   
    输入: [1,2,3]
    输出: [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

## 解题思路 ##

把数组长度看成坑位，选取数字填入坑位：

1.  检查手里剩下的数字有哪些
2.  选取其中一个填进当前的坑里

根据每个坑位的不同选择形成一个树结构，每条深度遍历路径对应着每种解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70]  
**递归式**：“重复”的内容，就是选数字填坑位这个动作。  
**递归边界**：这个重复递归式的动作一直持续到了最后一个数字也被填进坑里为止

## 代码实现： ##

/**
     * @param {number[]} nums
     * @return {number[][]}
     */
    // 入参是一个数组
    const permute = function(nums) {
      // 缓存数组的长度
      const len = nums.length
      // curr 变量用来记录当前的排列内容
      const curr = []
      // res 用来记录所有的排列顺序
      const res = []
      // visited 用来避免重复使用同一个数字
      const visited = {}
      // 定义 dfs 函数，入参是坑位的索引（从 0 计数）
      function dfs(nth) {
          // 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
          if(nth === len) {
              // 此时前 len 个坑位已经填满，将对应的排列记录下来
              res.push(curr.slice())
              return 
          }
          // 检查手里剩下的数字有哪些
          for(let i=0;i<len;i++) {
              // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
              if(!visited[nums[i]]) {
                  // 给 nums[i] 打个“已用过”的标
                  visited[nums[i]] = 1
                  // 将nums[i]推入当前排列
                  curr.push(nums[i])
                  // 基于这个排列继续往下一个坑走去
                  dfs(nth+1) 
                  // nums[i]让出当前坑位
                  curr.pop()
                  // 下掉“已用过”标识
                  visited[nums[i]] = 0
              }
          }
      }
      // 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
      dfs(0)
      return res
    };

# 例题-子集问题 #

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
    说明：解集不能包含重复的子集。

## 解题思路 ##

从每一个数字入手，讨论它出现或者不出现的情况

1.  递归式：检查手里剩下的数字有哪些，选取其中一个填进当前的坑里、或者干脆把这个坑空出来
2.  递归边界：组合里数字个数的最大值。拿示例来说，只给了 3 个数，因此组合里数字最多也只有 3 个，超过 3 个则视为触碰递归边界。

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

## 代码实现 ##

/**
     * @param {number[]} nums
     * @return {number[][]}
     */
    // 入参是一个数组
    const subsets = function(nums) {
        // 初始化结果数组
        const res = []   
        // 缓存数组长度
        const len = nums.length
        // 初始化组合数组
        const subset = []
        // 进入 dfs
        dfs(0)  
    
        // 定义 dfs 函数，入参是 nums 中的数字索引
        function dfs(index) {
            // 每次进入，都意味着组合内容更新了一次，故直接推入结果数组
            res.push(subset.slice())
            // 从当前数字的索引开始，遍历 nums
            for(let i=index;i<len;i++) {
                // 这是当前数字存在于组合中的情况
                subset.push(nums[i]) 
                // 基于当前数字存在于组合中的情况，进一步 dfs
                dfs(i+1)
                // 这是当前数字不存在与组合中的情况
                subset.pop()
            }
        }
        // 返回结果数组
        return res 
    };

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115831699][https_blog.csdn.net_qq_39903567_article_details_115831699]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70]: /images/20221022/b25804174b644c969bfaa7c47ab970e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70 1]: /images/20221022/ee8115cf6bf347d49434bb3fde9f52b7.png
[https_blog.csdn.net_qq_39903567_article_details_115831699]: https://blog.csdn.net/qq_39903567/article/details/115831699