4回溯法、空间状态树

2024-07-09 20:32:48| 来源: 网络整理| 查看: 265

回溯递归 1.递归的下面就是回溯的过程

2.回溯法是一个纯暴力的搜索

3.回溯法解决的问题：

3.1组合如：1234 两两组合 3.2切割问题如：一个字符串有多少个切割方式，或者切割出来是回文 3.3子集： 1 2 3 4 的子集 3.4排列问题（顺序） 3.5棋盘问题：n皇后解数独

4.回溯可抽象成树形结构树的宽度是集合的数目 for循环树的深度是递归的层数

void backtracking(){ 进入终止条件后开始 if(终止条件) { 收集结果 return //本层函数调用结束 } for(集合的元素集，类似子节点的个数) { 处理结点递归函数；回溯操作（撤销处理结点12， 2撤销，13 撤销3， 14） } return } 组合问题

1 2 3 4 比如求两个数的组合 12 13 14 23 24 34 可以两层for循环如果10个数求三个数的组合三层for循环 n个数求50个数的组合 50层for循环不合理所以用回溯（递归）来控制for循环的次数

树形结构在这里插入图片描述可以看出这个棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不在重复取。

第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

回溯三部曲

递归函数参数和返回值

确定终止条件

单层递归逻辑

递归函数参数和返回值参数二维数组result 存放最后结果一维数组path 存放路径上的值 n个数 k个数的组合 startindex 告诉递归每层从哪个数开始取比如在第二层中从234开始取

确定终止条件叶子节点结果的大小是2 path.size==k 收集path结果

单层递归逻辑先将节点i加入路径path 回溯（因为要进入下一层开始的结点是从i+1开始）撤回结点 path.pop()

private: vector result; // 存放符合条件结果的集合 vector path; // 用来存放符合条件结果 void backtracking(int n, int k, int startIndex) { if (path.size() == k) { result.push_back(path);//取一条路径上的结果 return; } for (int i = startIndex; i result.clear(); // 可以不写 path.clear(); // 可以不写 backtracking(n, k, 1); return result; } }; 组合问题剪枝

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了（因为只剩下3,4达不到4个数字）。在第二层for循环，从元素3开始的遍历都没有意义了。

即每一层的for循环从第二个数开始遍历的话，都没有意义。在这里插入图片描述「所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置」。「如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了」。

注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i private: vector result; vector path; void backtracking(int n, int k, int startIndex) { if (path.size() == k) { result.push_back(path); return; } for (int i = startIndex; i backtracking(n, k, 1); return result; } }; 组合总和

给定一个无重复元素的数组 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,2]为path 一维数组 result 二维数组，将符合的path放入result中 s为path内所有元素的和 target 目标和 startindex 开始的搜索的结点 candidate 集合

终止条件

if( s>target) //return if( s==target) result.push_back(path)//收集结果 return

单层搜索逻辑

for (int i = startIndex; i < candidates.size(); i++) {集合的长度 sum += candidates[i]; path.push_back(candidates[i]); backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数 sum -= candidates[i]; // 回溯 path.pop_back(); // 回溯 }

// 版本一 class Solution { private: vector result; vector path; void backtracking(vector& candidates, int target, int sum, int startIndex) { if (sum > target) { return; } if (sum == target) { result.push_back(path); return; } for (int i = startIndex; i result.clear(); path.clear(); backtracking(candidates, target, 0, 0); return result; } }; 状态空间树

在这里插入图片描述