《算法题讲解指南：递归，搜索与回溯算法--穷举vs深搜vs回溯vs剪枝》--12.全排列，13.子集

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录什么是回溯算法回溯算法的模板(不要死记硬背)回溯算法的应用12.全排列题目链接题目描述题目示例解法算法思路C算法代码算法总结及流程解析13.子集题目链接题目描述题目示例解法:算法思路:C算法代码(解法一决策树-当前位置选和不选)C算法代码(解法二决策树-i层的子集包含i个元素)算法总结及流程解析结束语什么是回溯算法回溯算法是一种经典的递归算法通常用于解决组合问题、排列问题和搜索问题等。回溯算法的基本思想从一个初始状态开始按照一定的规则向前搜索当搜索到某个状态无法前进时回退到前一个状态再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树通过遍历状态树来实现对所有可能解的搜索。回溯算法的核心思想“试错”即在搜索过程中不断地做出选择如果选择正确则继续向前搜索否则回退到上一个状态重新做出选择。回溯算法通常用于解决具有多个解且每个解都需要搜索才能找到的问题。回溯算法的模板(不要死记硬背)void backtrack(vectorint path, vectorint choice, ...) { // 满足结束条件 if (/* 满足结束条件 */) { // 将路径添加到结果集中 res.push_back(path); return; } // 遍历所有选择 for (int i 0; i choices.size(); i) { // 做出选择 path.push_back(choices[i]); // 做出当前选择后继续搜索 backtrack(path, choices); // 撤销选择 path.pop_back(); } }其中 path 表示当前已经做出的选择 choices 表示当前可以做的选择。在回溯算法中我们需要做出选择然后递归地调用回溯函数。如果满足结束条件则将当前路径添加到结果集中否则我们需要撤销选择回到上一个状态然后继续搜索其他的选择。回溯算法的时间复杂度通常较高因为它需要遍历所有可能的解。但是回溯算法的空间复杂度较低因为它只需要维护一个状态树。在实际应用中回溯算法通常需要通过剪枝等方法进行优化以减少搜索的次数从而提高算法的效率。回溯算法的应用组合问题组合问题是指从给定的一组数(不重复)中选取出所有可能的k个数的组合。例如给定数集[1,2,3]要求选取k2个数的所有组合。结果为1 [1,2]2 [1,3]3 [2,3]排列问题排列问题是指从给定的一组数(不重复)中选取出所有可能的k个数的排列。例如给定数集[1,2,3]要求选取k2个数的所有排列。结果为1 [1,2]2 [2,1]3 [1,3]4 [3,1]5 [2,3]6 [3,2]子集问题子集问题是指从给定的一组数中选取出所有可能的子集其中每个子集中的元素可以按照任意顺序排列。例如给定数集[1,2,3]要求选取所有可能的子集。结果为1 []2 [1]3 [2]4 [3]5 [1,2]6 [1,3]7 [2,3]8 [1,2,3]总结回溯算法是一种非常重要的算法可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单但是实现起来需要注意一些细节比如如何做出选择、如何撤销选择等。12.全排列题目链接46. 全排列 - 力扣LeetCode题目描述题目示例解法算法思路典型的回溯题目我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式不断地枚举每个数在当前位置的可能性并回溯到上一个状态直到枚举完所有可能性得到正确的结果。每个数是否可以放入当前位置只需要判断这个数在之前是否出现即可。具体地在这道题目中我们可以通过一个递归函数 backtrack和标记数组visited 来实现全排列。递归函数设计void backtrack(vectorvectorint res,vectorint nums,vectorbool visited,vectorint ans, int step, int len)参数step(当前需要填入的位置)len (数组长度)返回值无;函数作用查找所有合理的排列并存储在答案列表中。递归流程如下1.首先定义一个二维数组res用来存放所有可能的排列一个一维数组ans用来存放每个状态的排列一个一维数组visited 标记元素然后从第一个位置开始进行递归;2.在每个递归的状态中我们维护一个步数step表示当前已经处理了几个数字;3.递归结束条件当 step 等于 nums数组的长度时说明我们已经处理完了所有数字将当前数组存入结果中;4.在每个递归状态中枚举所有下标i若这个下标未被标记则使用nums数组中当前下标的元素:a.将visited[i]标记为 1;b.ans 数组中第 step个元素被nums[i]覆盖;c.对第step1个位置进行递归;d.将visited[i]重新赋值为0表示回溯;5.最后返回 res。特别地我们可以不使用标记数组直接遍历 step 之后的元素(未被使用)然后将其与需要递归的位置进行交换即可。C算法代码class Solution { public: vectorvectorint ret; bool check[7]; vectorint path; vectorvectorint permute(vectorint nums) { dfs(nums); return ret; } void dfs(vectorint nums) { if(path.size() nums.size()) { ret.push_back(path); return; } for(int i 0; i nums.size(); i) { if(check[i] false) { path.push_back(nums[i]); check[i] true; dfs(nums); path.pop_back(); check[i] false; } } } };算法总结及流程解析13.子集题目链接78. 子集 - 力扣LeetCode题目描述题目示例解法:算法思路:为了获得nums数组的所有子集我们需要对数组中的每个元素进行选择或不选择的操作即nums数组一定存在2^(数组长度)个子集。对于查找子集具体可以定义一个数组来记录当前的状态并对其进行递归。对于每个元素有两种选择:1.不进行任何操作;2.将其添加至当前状态的集合。在递归时我们需要保证递归结束时当前的状态与进行递归操作前的状态不变而当我们在选择进行步骤2进行递归时当前状态会发生变化因此我们需要在递归结束时撤回添加操作即进行回溯。递归函数设计void backtrack(vectorvectorint res,vectorint nums,vectorbool visited,vectorint ans, int step, int len)参数step(当前需要填入的位置)len (数组长度)返回值无;函数作用查找所有合理的排列并存储在答案列表中。递归流程如下:1.递归结束条件:如果当前需要处理的元素下标越界则记录当前状态并直接返回;2.在递归过程中对于每个元素我们有两种选择不选择当前元素直接递归到下一个元素;选择当前元素将其添加到数组末尾后递归到下一个元素然后在递归结束时撤回添加操作;3.所有符合条件的状态都被记录下来返回即可。C算法代码(解法一决策树-当前位置选和不选)class Solution { public: vectorvectorint ret; vectorint path; vectorvectorint subsets(vectorint nums) { dfs(nums, 0); return ret; } //解法一决策树-当前位置选和不选 void dfs(vectorint nums, int i) { if(i nums.size()) { ret.push_back(path); return; } //选择1不选当前值 dfs(nums, i 1); //选择2选择当前值 path.push_back(nums[i]); dfs(nums, i 1); //回溯-恢复现场 path.pop_back(); } };C算法代码(解法二决策树-i层的子集包含i个元素)class Solution { public: vectorvectorint ret; vectorint path; vectorvectorint subsets(vectorint nums) { dfs(nums, 0); return ret; } //解法二决策树-i层的子集包含i个元素 void dfs(vectorint nums, int index) { ret.push_back(path); for(int i index; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1); //回溯-恢复现场 path.pop_back(); } } };算法总结及流程解析结束语到此12.全排列13.子集 这两道算法题就讲解完了。全排列问题通过标记数组记录已使用元素子集问题则采用决策树方法处理每个元素的选/不选情况。两种解法都体现了回溯算法尝试-回溯的特点并强调了恢复现场的重要性。希望大家能有所收获