LeetCode-题目详解(十一):回溯算法【递归回溯、迭代回溯】【DFS是一个劲往某一个方向搜索;回溯算法建立在DFS基础之上,在搜索过程中,达到结束/裁剪条件后,恢复状态,回溯上一层,再次搜索】

本文主要是介绍LeetCode-题目详解(十一):回溯算法【递归回溯、迭代回溯】【DFS是一个劲往某一个方向搜索;回溯算法建立在DFS基础之上,在搜索过程中,达到结束/裁剪条件后,恢复状态,回溯上一层,再次搜索】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里写目录标题

  • 一、概述
    • 1、深度优先遍历(DFS) 和回溯算法区别
    • 2、 何时使用回溯算法
    • 3、回溯算法步骤
    • 4、回溯问题的类型
  • 二、LeetCode案例
    • 39. 组合总和
    • 40. 组合总和II
    • 77. 组合
    • 216. 组合总和 III
    • 46. 全排列
    • 47. 全排列 II
    • 剑指 Offer 38. 字符串的排列
    • 剑指 Offer II 079. 所有子集
    • 90. 子集 II
    • 剑指 Offer II 085. 生成匹配的括号【22. 括号生成】
    • 剑指 Offer II 086. 分割回文子字符串【131. 分割回文串】
    • 79. 单词搜索【剑指 Offer 12. 矩阵中的路径】
    • 面试题13. 机器人的运动范围
    • 面试题 08.10. 颜色填充

一、概述

1、深度优先遍历(DFS) 和回溯算法区别

DFS 是一个劲的往某一个方向搜索,而回溯算法建立在 DFS 基础之上的,但不同的是在搜索过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

「回溯法」实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就「回溯」返回,尝试别的路径。

回溯法是一种算法思想,而递归是一种编程方法,回溯法可以用递归来实现。

回溯法的整体思路是:搜索每一条路,每次回溯是对具体的一条路径而言的。对当前搜索路径下的的未探索区域进行搜索,则可能有两种情况:

  • 当前未搜索区域满足结束条件,则保存当前路径并退出当前搜索;
  • 当前未搜索区域需要继续搜索,则遍历当前所有可能的选择:如果该选择符合要求,则把当前选择加入当前的搜索路径中,并继续搜索新的未探索区域。

上面说的未搜索区域是指搜索某条路径时的未搜索区域,并不是全局的未搜索区域。

回溯法搜所有可行解的模板一般是这样的:

res = []
path = []def backtrack(未探索区域, res, path):if 未探索区域满足结束条件:res.add(path) # 深度拷贝returnfor 选择 in 未探索区域当前可能的选择:if 当前选择符合要求:path.add(当前选择)backtrack(新的未探索区域, res, path)path.pop()

2、 何时使用回溯算法

当问题需要 “回头”,以此来查找出所有的解的时候,使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通),要撤销选择,回退到上一个状态,继续尝试,直到找出所有解为止

3、回溯算法步骤

  1. 画出递归树,找到状态变量(回溯函数的参数),这一步非常重要※
  2. 根据题意,确立结束条件
  3. 找准选择列表(与函数参数相关),与第一步紧密关联※
  4. 判断是否需要剪枝
  5. 作出选择,递归调用,进入下一层
  6. 撤销选择

4、回溯问题的类型

在这里插入图片描述
注意:子集、组合与排列是不同性质的概念。子集、组合是无关顺序的,而排列是和元素顺序有关的,如 [1,2] 和 [2,1] 是同一个组合(子集),但 [1,2] 和 [2,1] 是两种不一样的排列!!!!因此被分为两类问题

二、LeetCode案例

39. 组合总和

给定一个无重复元素的数组 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 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

在这里插入图片描述

思路分析:根据示例 1:输入: candidates = [2, 3, 6, 7],target = 7。

  • 候选数组里有 2,如果找到了组合总和为 7 - 2 = 5 的所有组合,再在之前加上 2 ,就是 7 的所有组合;
  • 同理考虑 3,如果找到了组合总和为 7 - 3 = 4 的所有组合,再在之前加上 3 ,就是 7 的所有组合,依次这样找下去。

基于以上的想法,可以画出如下的树形图。建议大家自己在纸上画出这棵树,这一类问题都需要先画出树形图,然后编码实现。

编码通过 深度优先遍历 实现,使用一个列表,在 深度优先遍历 变化的过程中,遍历所有可能的列表并判断当前列表是否符合题目的要求,成为「回溯算法」(个人理解,非形式化定义)。

在这里插入图片描述

  • 以 target = 7 为 根结点 ,创建一个分支的时 做减法 ;
  • 每一个箭头表示:从父亲结点的数值减去边上的数值,得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值;
  • 减到 00 或者负数的时候停止,即:结点 00 和负数结点成为叶子结点;
  • 所有从根结点到结点 00 的路径(只能从上往下,没有回路)就是题目要找的一个结果。

这棵树有 44 个叶子结点的值 00,对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]],而示例中给出的输出只有 [[7], [2, 2, 3]]。即:题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。

产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。

一种简单的去重方案是借助哈希表的天然去重的功能,但实际操作一下,就会发现并没有那么容易。

可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 按某种顺序搜索。具体的做法是:每一次搜索的时候设置 下一轮搜索的起点 begin,请看下图。

在这里插入图片描述
即:从每一层的第 22 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。

如果题目要求,结果集不计算顺序,此时需要按顺序搜索,才能做到不重不漏。「力扣」第 47 题( 全排列 II )、「力扣」第 15 题( 三数之和 )也使用了类似的思想,使得结果集没有重复。

在这里插入图片描述

回溯算法模板【Python】:

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.result = []self.path = []self.back_tracking(candidates, target, 0, 0)return self.resultdef back_tracking(self, nums, target, total, start):if total > target:returnif total == target:curr_path = self.path[:]    # 对于python来说,必不可少self.result.append(curr_path)returnfor i in range(start, len(nums)):self.path.append(nums[i])total += nums[i]self.back_tracking(nums, target, total, i)self.path.pop()total -= nums[i]

回溯算法模板【C++】:

class Solution {
public:vector<vector<int>> result;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backTracking(candidates, target, 0, 0);return result;}void backTracking(vector<int>& nums, int target, int total, int start){if(total > target){return;}if(total == target){result.push_back(path);return;}for(int i = start; i < nums.size(); i++){path.push_back(nums[i]);total += nums[i];backTracking(nums, target, total, i);path.pop_back();total -= nums[i];}}
};

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result = []# 回溯算法def dfs(nums, temp_target, path):# 递归结束条件if temp_target < 0:return# 逻辑主体部分if temp_target == 0:result.append(path)# 递归for idx, num in enumerate(nums):dfs(nums[idx:], temp_target - num, path + [num])dfs(candidates, target, [])return result
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.result = []self.dfs(candidates, target, [])return self.resultdef dfs(self, nums, target, path):if sum(path) > target:returnif sum(path) == target:self.result.append(path)returnfor idx, num in enumerate(nums):self.dfs(nums[idx:], target, path + [num])

剪枝提速

  • 根据上面画树形图的经验,如果 target 减去一个数得到负数,那么减去一个更大的树依然是负数,同样搜索不到结果。基于这个想法,我们可以对输入数组进行排序,添加相关逻辑达到进一步剪枝的目的;
  • 排序是为了提高搜索速度,对于解决这个问题来说非必要。但是搜索问题一般复杂度较高,能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况,都试一下。

回溯算法模板【Python】:

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.result = []self.path = []candidates.sort()   # 排序不是必须操作self.back_tracking(candidates, target, 0, 0)return self.resultdef back_tracking(self, nums, target, total, start):if total > target:returnif total == target:curr_path = self.path[:]    # 对于python来说,必不可少self.result.append(curr_path)returnfor i in range(start, len(nums)):self.path.append(nums[i])total += nums[i]self.back_tracking(nums, target, total, i)self.path.pop()total -= nums[i]

回溯算法模板【C++】:

class Solution {
public:vector<vector<int>> result;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 排序不是必须操作backTracking(candidates, target, 0, 0);return result;}void backTracking(vector<int>& nums, int target, int total, int start){if(total > target){return;}if(total == target){result.push_back(path);return;}for(int i = start; i < nums.size(); i++){path.push_back(nums[i]);total += nums[i];backTracking(nums, target, total, i);path.pop_back();total -= nums[i];}}
};

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result = []# 回溯算法def dfs(nums, temp_target, path):# 递归结束条件【剪枝:如果当前temp_target < 0,没必要枚举了,直接return】if temp_target < 0:return# 逻辑主体部分if temp_target == 0:result.append(path)# 递归for idx, num in enumerate(nums):# 在搜索的时候就去重:这一类相同元素不计算顺序的问题,我们在搜索的时候就按某种顺序搜索。# 从每一层的第 2 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。dfs(nums[idx:], temp_target - num, path + [num])candidates.sort()   # 排序不是必须操作dfs(candidates, target, [])return result

40. 组合总和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

  • 所有数字(包括目标数)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[[1,2,2],[5]
]

一句话题解:按顺序搜索,设置合理的变量,在搜索的过程中判断是否会出现重复集结果。

与第 39 题(组合之和)的差别:

  • 第 39 题:candidates 中的数字可以无限制重复被选取;
  • 第 40 题:candidates 中的每个数字在每个组合中只能使用一次。

相同点是:相同数字列表的不同排列视为一个结果。

为了避免产生重复解,本题candidates务必排序。

如何去掉重复的集合(重点),为了使得解集不包含重复的组合。有以下 2 种方案:

  • 使用 哈希表 天然的去重功能,但是编码相对复杂;
  • 这里我们使用和第 39 题和第 15 题(三数之和)类似的思路:不重复就需要按 顺序 搜索, 在搜索的过程中检测分支是否会出现重复结果 。注意:这里的顺序不仅仅指数组 candidates 有序,还指按照一定顺序搜索结果。

在这里插入图片描述
在这里插入图片描述
由第 39 题我们知道,数组 candidates 有序,也是 深度优先遍历 过程中实现「剪枝」的前提。

将数组先排序的思路来自于这个问题:去掉一个数组中重复的元素。很容易想到的方案是:先对数组 升序 排序,重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。也就是说,剪枝发生在:同一层数值相同的结点第 2、3 … 个结点,因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果,同一层的其它结点,候选数的个数更少,搜索出的结果一定不会比第 1 个结点更多,并且是第 1 个结点的子集。

class Solution:def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:self.result = []nums.sort() # 排序是必须操作self.dfs(nums, target, [])return self.result# 回溯算法def dfs(self, nums, target, path):# 递归结束条件【剪枝:如果当前total > target,没必要枚举了,直接return】if target < 0:return# 逻辑主体部分if target == 0:self.result.append(path)# 递归for idx, num in enumerate(nums):# 在搜索的时候就去重:这一类相同元素不计算顺序的问题,我们在搜索的时候就按某种顺序搜索。# 从每一层的第 2 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。# 而且重复的元素要跳过,防止产生重复数组if idx > 0 and nums[idx] == nums[idx - 1]:continueself.dfs(nums[idx + 1:], target - num, path + [num])    

回溯算法模板【Python】:

class Solution:def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:self.result = []self.path = []nums.sort() # 排序是必须操作self.back_tracking(nums, target, 0, 0)return self.result# 回溯算法def back_tracking(self, nums, target, total, start):# 递归结束条件【剪枝:如果当前total > target,没必要枚举了,直接return】if total > target:return# 逻辑主体部分if total == target:curr_path = self.path[:]    # 深拷贝self.result.append(curr_path)# 递归for i in range(start, len(nums)):# 在搜索的时候就去重:这一类相同元素不计算顺序的问题,我们在搜索的时候就按某种顺序搜索。# 从每一层的第 2 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。# 而且重复的元素要跳过,防止产生重复数组if i > start and nums[i] == nums[i - 1]:continueself.path.append(nums[i])total += nums[i]self.back_tracking(nums, target, total, i + 1)self.path.pop()total -= nums[i]

回溯算法模板【C++】:

class Solution {
public:vector<vector<int>> result; // 存放组合集合vector<int> path;           // 符合条件的组合vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());backTracking(candidates, target, 0, 0);return result;}void backTracking(vector<int>& nums, int target, int total, int start){// 递归结束条件【剪枝:如果当前total < 0,没必要枚举了,直接return】if(total > target){return;}// 逻辑主体部分if(total == target){result.push_back(path);}// 递归for(int i = start; i < nums.size(); i++){// 要对同一树层使用过的元素进行跳过if(i > start && nums[i] == nums[i - 1]){continue;}//记忆【将当前元素加入到path中】path.push_back(nums[i]);total += nums[i];backTracking(nums, target, total, i + 1);// 回溯【将当前元素从path删除】path.pop_back();total -= nums[i];}}
};
class Solution {
public:vector<vector<int>> result; // 存放组合集合vector<int> path;           // 符合条件的组合vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());backTracking(candidates, target, 0, 0);return result;}void backTracking(vector<int>& nums, int target, int total, int start){// 递归结束条件【剪枝:如果当前total < 0,没必要枚举了,直接return】if(total > target){return;}std::cout << "total = " << total << "; ";std::cout << "path = [";for(auto num: path) {std::cout << num;}std::cout << "]" << std::endl;// 逻辑主体部分if(total == target){result.push_back(path);}// 递归for(int i = start; i < nums.size(); i++){// 要对同一树层使用过的元素进行跳过if(i > start && nums[i] == nums[i - 1]){continue;}//记忆【将当前元素加入到path中】path.push_back(nums[i]);total += nums[i];backTracking(nums, target, total, i + 1);// 回溯【将当前元素从path删除】path.pop_back();total -= nums[i];}

这篇关于LeetCode-题目详解(十一):回溯算法【递归回溯、迭代回溯】【DFS是一个劲往某一个方向搜索;回溯算法建立在DFS基础之上,在搜索过程中,达到结束/裁剪条件后,恢复状态,回溯上一层,再次搜索】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128821

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1565(状态压缩)

本人第一道ac的状态压缩dp,这题的数据非常水,很容易过 题意:在n*n的矩阵中选数字使得不存在任意两个数字相邻,求最大值 解题思路: 一、因为在1<<20中有很多状态是无效的,所以第一步是选择有效状态,存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值,状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个