正文

算法-回溯回溯总结(代码片段)

flix  flix  2023-03-22  356

关键词：

什么是回溯

在求解诸如八皇后、全排列等问题时，我们通常使用深度优先搜索dfs在解空间内搜索满足条件的解，dfs的搜索过程可以看做是在一棵搜索树上遍历的过程。例如，求数字[1,2,3]的全排列的搜索树如下：
技术图片
当我们搜索到树的深层向浅层返回的过程就是回溯。
（我认为可以这样理解：从上往下搜索是递归，从下往上返回是回溯。当然，这不一定正确。）

为什么需要回溯

继续拿求[1,2,3]的全排列举例，我们搜索到树的底部得到了一个排列123，这时我们需要返回到上一层继续进行搜索。如果不回溯的话，那么就无法遍历整棵搜索树，也就无法求得全部的解。一般在两种情况下程序需要回溯：

找到了一个满足要求的解；
当前层递归找不到满足要求的解，回溯到上一层寻找。例如，在八皇后问题中，如果当前行找不到一个满足条件的位置，可以回溯到上一行，调整上一行皇后的位置，然后继续递归。

模板

大多回溯问题都遵循一个通用的模板，总体的步骤就是做选择、递归到下一层、撤销选择、回溯。

void backtrack(参数)	// start是做选择的起始位置
	if(满足条件)
		将当前结果加入答案中；
		return;
	
	
	for(选择 in 所有选择)
		做选择；
		backtrack(参数)；
		撤销选择；

更详细一点的表述如下：

void backtrack(start, 其他参数)	// start是做选择的起始位置
	if(满足条件)
		将当前结果加入答案中；
		return;
	
	
	for(int i=start; i<n; i++)
		if(满足剪枝条件) continue;
		做选择；
		backtrack(i, 其他参数)；
		撤销选择；

例如，求一个数组的所有子集的代码如下：

class Solution 
public:
    vector<vector<int>> subsets(vector<int>& nums) 
        if(nums.empty()) return ;

        vector<vector<int>> ans;
        vector<int> track;
        backtrack(nums, 0, track, ans);
        return ans;
    

    void backtrack(vector<int> nums, int start, vector<int> track, vector<vector<int>>& ans)
        ans.push_back(track);

        for(int i=start; i<nums.size(); i++)
            track.push_back(nums[i]);
            backtrack(nums, i+1, track, ans);
            track.pop_back();
        
    
;

可以看出，直接套用模板即可。

技巧

不同的回溯题的区别主要在两点：

从哪个地方开始做选择，也就是每次递归start的设置问题。
有一些问题要求答案中不能包含重复的解，这个是如何剪枝从而去重的问题。

问题1

首先看第一个问题，就是从哪个地方开始做选择，也就是每次递归的时候start如何设置。在全排列这题当中，我们每次递归都从数组第1个数字开始选择，而在子集这题中，我们每次都从上一次选择的位置的下一个位置开始选择。如果在做当前的选择时要考虑之前的选择，那么就要把每次递归的start设为0；如果在做当前选择的时候只考虑当前的选择以及之后的选择，那么就把start设为上一个选择的下一个位置i+1或者i。
上面的结论其实不是很准确，还是要根据不同的情况来调整。这里记录几个与start选择相关的题目：全排列、子集、组合总和和组合总和II。

问题2

当题目中要求答案中不能包含重复的解时，通常意味着要加入去重操作。为了便于去重，通常在搜索之前先对数组进行排序。举个例子，在全排列II中，数组中可能包含重复数字，例如[1,1,2]，而要求答案中不包含重复的排列。经过分析可以发现，出现重复的原因是因为在同一层递归中出现了相同的数字。所以，为了去重，我们在同一层递归的迭代中，要找到和之前不相同的数字继续搜索。
相关题目：全排列II、子集II、组合总和II。

编号	题目	难度
1	全排列	中等
2	全排列II	中等
3	子集	中等
4	子集II	中等
5	组合总和	中等
6	组合总和II	中等
7	字母大小写全排列	简单
8	电话号码的字母组合	中等
9	N皇后	困难

其他

下面的链接对回溯有更详细的解释：

回溯算法及题目(代码片段)

目录前言一.什么是回溯算法 1.1概念 1.2理解回溯 1.3 模板 1.4回溯算法可以解决的问题组合问题分割问题求子集问题排列问题重新安排行程前言本博客参考代码随想录的题目来编写，大家可以... 查看详情

回溯算法(代码片段)

回溯算法回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但... 查看详情

回溯算法(代码片段)

百度百科解释:回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目... 查看详情

深入浅出回溯算法(代码片段)

一，如何理解回溯算法深度优先搜索算法利用的就是回溯算法思想，但它除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。除此之... 查看详情

回溯算法-组合(代码片段)

原题https://leetcode.cn/problems/combinations/思路回溯算法实际上就是深度优先算法的一种。也就是说，当我们在使用一个深度优先算法（一般用递归）的时候，有时候操作完一个步骤需要回退到上一步，这就叫回溯... 查看详情

回溯算法-组合(代码片段)

算法入门（回溯算法）(代码片段)

...递归后，就可以来学习与理解它好兄弟回溯了。回溯算法比较抽象，小编就以自己学习的角度来分析了！回溯与递归有什么关系递归与回溯是相辅相成的，回溯算法在递归之后，（可以理解没有递归就... 查看详情

算法----leetcode回溯系列问题题解(代码片段)

回溯法回溯1.什么是回溯?2.回溯法解决的问题3.回溯法的模板LeetCode题目列表组合问题77.组合216组合总和III17.电话号码的字母组合39.组合总和40.组合总和II分割问题131.分割回文串93.复原IP地址子集问题78.子集90.子集II排列问题46.全... 查看详情

数据结构与算法--回溯算法(代码片段)

1、八皇后问题//8皇后问题--回溯算法publicclassRecallint[]result=newint[8];//全局或成员变量，下标表示行，值表示queue存储在哪一列publicstaticvoidmain(String[]args)Recallrecall=newRecall();recall.cal8queues(0);publicvoidcal8queues(introw) 查看详情

初识“回溯算法”讲解及leetcode对应例题解析(代码片段)

初识“回溯算法”讲解及LeetCode对应例题解析回溯算法1、回溯算法的概念2、回溯算法的一般解题思路3、解决问题的方法例题一：二叉树中和为某一值的路径（1）题目描述（2）题目分析（3）代码实现... 查看详情

初识“回溯算法”讲解及leetcode对应例题解析(代码片段)

数据结构&算法-回溯算法&贪心算法(代码片段)

回溯算法概念（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不... 查看详情

算法模板-回溯(代码片段)

...#xff0c;它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都比较高。解题模板回溯算法的解题一般是递归实现查看详情

算法模板-回溯(代码片段)

...#xff0c;它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都比较高。解题模板回溯算法的解题一般是递归实现查看详情

回溯法解决八皇后问题(代码片段)

八皇后问题是学习回溯算法时不得不提的一个问题，用回溯算法解决该问题逻辑比较简单。下面用java版的回溯算法来解决八皇后问题。八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例... 查看详情

回溯算法python(代码片段)

...编码括号生成电话号码的字母组合组合总和参考前言回溯算法其实就是我们常说的DFS算法，本质上就是一种暴力穷举算法。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过... 查看详情

回溯算法套路详解（转）(代码片段)

...后面会用「全排列」和「N皇后问题」这两个经典的回溯算法问题来查看详情

回溯算法刷题合集(代码片段)

回溯算法刷题合集组合问题77.组合给定两个整数n和k，返回1…n中所有可能的k个数的组合。示例:输入:n=4,k=2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]//回溯算法求组合问题：//1.首先构建数组存放要返回的值//2.判断递归结束... 查看详情