做情网站,wordpress改变底部logo,建站快车的使用方法,网址提交收录所有题目均来自于LeetCode#xff0c;刷题代码使用的Python3版本 回溯算法
回溯算法是一种搜索的方法#xff0c;在二叉树总结当中#xff0c;经常使用到递归去解决相关的问题#xff0c;在二叉树的所有路径问题中#xff0c;我们就使用到了回溯算法来找到所有的路径。
… 所有题目均来自于LeetCode刷题代码使用的Python3版本 回溯算法
回溯算法是一种搜索的方法在二叉树总结当中经常使用到递归去解决相关的问题在二叉树的所有路径问题中我们就使用到了回溯算法来找到所有的路径。
回溯算法本质就是去穷举性能并不是那么高效。一般为了提高效率往往回溯算法会跟剪枝操作相结合。
回溯算法通常可以用来解决一些问题这也是为什么会有回溯算法的原因
组合问题 N个数里面按照一定规则找出k个数的集合。组合不强调元素的顺序 切割问题 一个字符串按一定规则有几种切割方式 分割回文串复原IP地址 子集问题 一个N个数的集合里有多少符合条件的子集 排列问题 N个数按照一定规则全排列有几种排列方式。排列强调元素的顺序 棋盘问题 N皇后、解数独问题
理解回溯
回溯法解决的问题都可以抽象为树形结构回溯算法解决问题都是在集合中递归查找子集集合的大小构成了树的宽度递归的深度构成了树的深度。
递归必须要有终止条件所以一定是一个高度有限的N叉树。
回溯模板
递归三部曲
返回值及参数 void backtracking(参数) 回溯函数的终止条件回溯搜索的遍历过程
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}练习题
77、组合 class Solution:def combine(self, n: int, k: int) - List[List[int]]:def backtracking(n,k,startindex,path):if len(path)k:# 这里需要注意因为列表在Python中是可变数据类型后面的修改会导致path变为[]res.append(path[:])return # 这里的startindex代表的是在单层递归中需要遍历的次数 从startindex一直到n寻找符合条件的数for i in range(startindex, n1):path.append(i)backtracking(n,k,i1,path)a path.pop()res []backtracking(n,k,1,[])return res回溯剪枝
使用剪枝的原理就在于如果剩余的元素个数已经小于k-len(path)的时候我们就不再往下继续了。
已经选择过的元素个数len(path)还需要选择的个数k-len(path)在集合中更需要从最多要从下标为n-(k-len(path))1开始遍历在python中因为range循环的时候是左闭右开所以还需要1 class Solution:def combine(self, n: int, k: int) - List[List[int]]:def backtracking(n,k,startindex,path):if len(path)k:# print(path)# 这里需要注意因为列表在Python中是可变数据类型后面的修改会导致path变为[]res.append(path[:])return for i in range(startindex, n-(k-len(path))11):path.append(i)backtracking(n,k,i1,path)# 回溯 退出上一个元素path.pop()res []backtracking(n,k,1,[])return res2024更新代码【传递的参数不要过多题目已经给出的参数就不需要再进行传递了】
class Solution:def combine(self, n: int, k: int) - List[List[int]]:res []def backtracking(startIndex, path):if len(path) k:res.append(path[:])returnfor i in range(startIndex, n - (k - len(path)) 1 1):path.append(i)backtracking(i 1, path)path.pop()backtracking(1, [])return res216、组合总数III 利用回溯代码模板。其中需要注意的是如果path列表的和已经超过n那么可以直接进行剪枝除此之外如果剩余的数字长度小于k-len(path)的话就可以不用继续循环了这一点也方便我们进行剪枝。
递归的三要素
返回值和参数
def backtracking(n,k,startindex,path):pass递归终止条件
if sum(path)n:return
if len(path)k and sum(path)n:res.append(path[:])return递归体部分
for i in range(startindex,9 - (k - len(path)) 1 1):path.append(i)backtracking(n,k,i1,path)path.pop()代码
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:def backtracking(n,k,startindex,path):# 剪枝if sum(path)n:return if len(path)k and sum(path)n:res.append(path[:])returnfor i in range(startindex,9 - (k - len(path))11):path.append(i)backtracking(n,k,i1,path)path.pop()res []backtracking(n,k,1,[])return res17、电话号码的字母组合 思路
本题类似于组合问题需要根据输入的数字对其能够涵盖的字母进行组合需要解决下面几个问题
数字和字母如何进行映射 采用一个列表位置0和位置1的地方空出来从2开始对应号码上的字母用字符串表示 两个字母两个for循环三个字母三个for循环多个字母多个for循环输入异常字母如何进行处理 对于空的digits需要返回一个空列表
递归三要素
递归的参数
参数是digits和index其中digits是题目给出的字符串如“23”而index是记录当前已经遍历到第几个数字了。【实际可以不用digits】
递归结束的条件
如果index的长度和digits长度一样的话直接return
if indexlen(digits):res.append(path) # 这里的path被定义为字符串 而字符串在python中是不可变数据类型因此可以直接用return递归体部分
需要注意的是回溯的时候对于字符串要想去掉最后一个字符的方法是直接ss[:-1]。
# 获取字符串中的数字
mynum int(digits[index])
# 获取电话号码对应的字符组合
char myhash[mynum]
for i in range(len(char)):pathchar[i]backtracking(digits, index1, path)path path[:-1] # 刨去字符串的最后一个字符本题是不需要startindex的因为遍历的不是同一个集合而是不同的集合。在回溯问题中如果是遍历同一个集合就需要传递一个参数startindex用来表示的当前遍历到集合中的第几位。
本题通过index来判断目前遍历到第几个数字并且index是通过充当函数的参数来实现的。
class Solution:def letterCombinations(self, digits: str) - List[str]:myhash [,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz]res []s def backtracking(digits, index):nonlocal sif indexlen(digits):res.append(s)return # digit表示digits中的数字digit int(digits[index])# letters表示digit所代表的数字对应的字母有哪些letters myhash[digit]# for循环遍历这些字母 for i in range(len(letters)):sletters[i]# 进行回溯backtracking(digits,index1)s s[:-1]if len(digits)0:return resbacktracking(digits,0)return res本题有一个需要特殊处理的地方如果digits为空字符串的话直接返回空列表不需要在进行递归回溯了。 class Solution:def letterCombinations(self, digits: str) - List[str]:if len(digits)0:return []numList [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]res []s def backtracking(index):nonlocal sif len(digits) len(s):res.append(s)returndigit int(digits[index])chars numList[digit]for i in range(len(chars)):schars[i]backtracking(index1)s s[:-1]backtracking(0)return res39、组合总数 本题中说了candidates中的同一个数字可以无限制重复被选取所以我们在进行递归的时候传递的startindex就是i。
这里需要注意的是每次需要传入startIndex的原因是可以避免选取之前已经取过的数字 本题中需要注意及时剪枝即当sum_target之后就可以不用往下进行回溯了并且可以使用一个累加的sum_代替掉使用内置的sum方法节省时间开销。
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:res []sum_ 0def backtracking(startIndex, path):nonlocal sum_if sum_ target:returnif sum_ target:res.append(path[:])returnfor i in range(startIndex, len(candidates)):path.append(candidates[i])sum_ candidates[i]backtracking(i, path)sum_ - path.pop()backtracking(0, [])return res40、组合总数II* 本题需要注意的是跟前面不同的地方在于每个数字在每个组合中只能使用一次同时在解集中不能包含重复的组合。因此想到设置一个used数组来表示每个元素是否已经被访问过。 此处也可以不使用used数组
其中candidates数组需要进行排序这样能够保证如果数字相同的情况下只会使用一次。 要去重的是同一层上是否使用过可以看出在candidates[i] candidates[i - 1]相同的情况下
used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过 class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:res [] # 用于记录返回结果sum_ 0def backtracking(candidates,target,path,startindex,used):nonlocal sum_if sum_target:return if sum_target:res.append(path[:])return for i in range(startindex,len(candidates)):if istartindex and candidates[i]candidates[i-1] and not used[i-1]:continuepath.append(candidates[i])sum_candidates[i]used[i]Truebacktracking(candidates,target,path,i1,used)sum_-candidates[i]used[i]Falsepath.pop()# candidates需要进行排序否则相同的数字可能不会连续candidates.sort()backtracking(candidates,target,[],0,[False]*len(candidates))return res优化 不使用used数组
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:res []def backtracking(candidates,target,startindex,sum_,path):if sum_target:res.append(path[:])returnfor i in range(startindex, len(candidates)):if istartindex and candidates[i]candidates[i-1]:continuesum_candidates[i]# 这里进行判断如果超过target则直接break 免去了后面的循环 节省时间开销 if sum_ target:breakpath.append(candidates[i])backtracking(candidates,target,i1,sum_,path)sum_-candidates[i]path.pop()candidates.sort()backtracking(candidates,target,0,0,[])return resclass Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:res []sum_ 0def backtracking(startIndex, path):nonlocal sum_if sum_ target:returnif sum_ target:res.append(path[:])returnfor i in range(startIndex, len(candidates)):if i startIndex and candidates[i] candidates[i - 1]:continuepath.append(candidates[i])sum_ candidates[i]backtracking(i 1, path)sum_ - path.pop()candidates.sort()backtracking(0, [])return res131、分割回文串* 本题递归结束的条件是当startindex字符串s 的长度时往结果集中添加数据并返回。
递归的参数是startindex和path需要进行递归的字符串为s[startindex:i1]进行切片同时本题要求是回文子串所以还需要加上判断是否是回文数字如果是回文数字才进行回溯不是回文数字的话不进行任何操作。
在递归体部分需要一个for循环其遍历范围是startindex到len(s)然后往path列表中添加的元素是s[startindex:i1]这里注意字符串的切片是左闭右开的因此这里区间是i1然后递归进行遍历backtracking(s,i1,path)注意这里的startindex需要从i1开始这是因为根据题目的要求不会有重复出现的子串。
在**【39、组合总数】**一题中题目说明candidates中的元素是可以重复出现的因此我们在进行递归的时候传入的startindex就为for循环遍历的层数i这样就可以一直递归下去找到符合条件的答案。但是本题中不能出现重复的所以传入的参数是i1
递归三要素
参数和返回值
def backtracking(s, startindex, path):递归终止条件
if startindexlen(s):res.append(path[:])return递归体 单层搜索过程
for i in range(startindex,len(s)):if huiwen(s[startindex:i1]):path.append(s[startindex:i1])backtracking(s,i1,path)path.pop()全部代码
class Solution:def partition(self, s: str) - List[List[str]]:res []def backtracking(s,startindex,path):# print(startindex)# 如果分割到字符串末尾则该轮结束if len(s)startindex:res.append(path[:])for i in range(startindex,len(s)):# print(s[startindex:i1])# 如果不是回文子串 不往path中添加if huiwen(s[startindex:i1]):path.append(s[startindex:i1])backtracking(s,i1,path)path.pop()def huiwen(s):return True if ss[::-1] else False# i 0# j len(s)-1# while ij:# if s[i]!s[j]:# return False# i1# j-1# return Truebacktracking(s,0,[])return res93、复原IP地址* 本题与分割字符串有几分相似也属于分割问题。
递归三要素
递归参数
字符串sstartindex和pointNum
pointNum表示IP地址中的.如果有三个.的话就说明当前的IP地址已经被分成四段了。
递归结束的条件
根据本题要求只要我们当前的字符串已经被分割成四段即pointNum3的时候往res列表中添加结果并返回
单层递归体中的操作
for i in range(startindex, len(s)):# IP 地址合法性剪枝if isValid(s[startindex:i1]):sub s[startindex:i1]# 这里不能直接修改 path而是使用一个副本进行传参backtracking(i 1, path sub ., pointNum 1)else:break校验逻辑
每一段以0开头则不合法每一段有非正整数数字不合法每一段数字如果大于255则不合法
def isValid(s):if len(s) 0 or (s[0] 0 and len(s) 1) or int(s) 255:return Falsereturn True完整代码
class Solution:def restoreIpAddresses(self, s: str) - List[str]:res []def backtracking(startindex, path, pointNum):# 长度剪枝if len(s) - startindex (4 - pointNum) * 3:returnif len(s) - startindex (4 - pointNum):returnif pointNum 3:if isValid(s[startindex:]):res.append(path s[startindex:])returnfor i in range(startindex, len(s)):# IP 地址合法性剪枝if isValid(s[startindex:i1]):sub s[startindex:i1]# 这里不能直接修改 path而是使用一个副本进行传参backtracking(i 1, path sub ., pointNum 1)else:breakdef isValid(s):if len(s) 0 or (s[0] 0 and len(s) 1) or int(s) 255:return Falsereturn Truebacktracking(0, , 0)return res78、子集 思路
如果把子集问题抽象成一颗树的话组合问题和分割问题都是收集树的叶子结点子集问题是找树的所有结点。 子集是无序的{1,2}和{2,1}是等价的也就是说之前取过的元素后面不会再取因此在递归的过程中还需要传递一个参数startindex每次都是从startindex继续往后进行搜索而不是从0开始如果是排列问题的话for循环就要从0开始了因为在排列中{1,2}和{2,1}是两个不一样的排列。
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:res []def backtracking(nums,startindex,path):res.append(path[:])# 这里不需要加递归结束的条件当startindex达到len(nums)的时候程序也就自动返回了for i in range(startindex,len(nums)):path.append(nums[i])backtracking(nums,i1,path)path.pop()backtracking(nums,0,[])return res90、子集II* 本题和上一题的区别在于nums数组中可能包含重复元素我们首先将其进行排序然后在往res列表中添加数据的时候进行判断只有不在res列表中的结果才能添加进去。其余部分和上一题一样。
使用in操作去重
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:# nums list(set(nums))res []def backtracking(nums, startindex, path):if path not in res:res.append(path[:])if startindexlen(nums):returnfor i in range(startindex,len(nums)):path.append(nums[i])backtracking(nums,i1,path)path.pop()nums.sort()backtracking(nums,0,[])return res本题是树层去重在同一层重复出现的需要去除重复值树层去重的话需要对数组进行排序。 直接判断去重
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:res []def backtracking(startIndex, path):res.append(path[:])for i in range(startIndex, len(nums)):if i startIndex and nums[i] nums[i - 1]:continuepath.append(nums[i])backtracking(i 1, path)path.pop()nums.sort()backtracking(0, [])return res使用used数组去重推荐
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:res []used [False]*len(nums)def backtracking(nums,startindex,path,used):res.append(path[:])if startindex len(nums):return for i in range(startindex,len(nums)):if i0 and nums[i]nums[i-1] and not used[i-1]:continueused[i] Truepath.append(nums[i])backtracking(nums,i1,path,used)used[i] Falsepath.pop()nums.sort()backtracking(nums,0,[],used)return res491、递增子序列* 本题需要再输入的序列中找到全部的递增子序列同时需要注意的是题目中输入的数组会包含重复的元素并且说明如果出现两个整数相等也会看作是递增序列的一种特殊情况。
利用回溯的思路我们写出递归的三要素
参数和返回值
参数有startindex用于记录下一层遍历的起始位置 path 用于记录结果列表
def backtracking(startindex, path):递归终止条件
题目中要求递增子序列中至少2个元素因此可以判断如果len(path)1则往res列表中添加结果并返回
这里需要注意不能加return加上了return的话就会导致同一个树枝上的其他结果不能得到保存这点类似于子集问题子集问题是需要寻找叶子上的节点。
if len(path)1:res.append(path[:])# return 单层搜索逻辑
本题需要寻找递增子序列不像之前的题目可以直接通过排序解决去重问题因此需要使用另一种去重的方式使用python中的集合在Python中集合也是一个哈希表可以在O(1)时间复杂度查询到想要的结果。
这里注意条件是和递增是或者or的关系的即如果该数字已经在uset中说明已经使用过了需要跳过该数字。
同时uset是在每一层都会重新进行定义的uset只会负责本层的结果。同一个父节点下的一层内如果出现重复数字则直接跳过
这里的一层指的是节点拥有同一个父节点 uset set()
for i in range(startindex, len(nums)):if (path and path[-1]nums[i]) or nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])backtracking(nums,i1,path)path.pop()完整代码
class Solution:def findSubsequences(self, nums: List[int]) - List[List[int]]:res []def backtracking(startIndex, path):if len(path) 1:res.append(path[:])uset set()for i in range(startIndex, len(nums)):if (path and path[-1] nums[i]) or nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])backtracking(i 1, path)path.pop()backtracking(0, [])return res 46、全排列 全排列和组合问题、切割问题以及子集问题的区别就在于每次遍历都需要从0开始而不是传进来的startindex也就是说全排列问题中是不需要startindex的。
另外在之前的几种问题中有几个我们传入参数不是i1而是i的这是因为题目中说明可以出现重复元素。如果要求是不能出现重复元素的话只能传入i1。
本题中因为下标都是从0开始进行遍历的所以就需要记录哪些数字之前已经被使用过了所以这里有两个方法
使用used数组进行记录使用uset集合进行记录
上面的这两种方法都需要在函数的参数中进行传递
递归三部曲
参数和返回值
def backtracking(path,used):递归终止条件
if len(path)len(nums):res.append(path[:])return 单层搜索逻辑
for i in range(0, len(nums)):if used[i]:continueused[i]Truepath.append(nums[i])backtracking(nums,path)used[i]Falsepath.pop()完整代码
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []used [False] * len(nums)def backtracking(path, used):if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):if used[i]:continueused[i] Truepath.append(nums[i])backtracking(path, used)path.pop()used[i] Falsebacktracking([], used)return res使用uset集合避免使用个重复的数组
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []def backtracking(path, uset):if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):if nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])backtracking(path, uset)uset.remove(path.pop())backtracking([], set())return res47、全排列II* 本题因为nums中包含重复的数字因此需要去重去重的时候因为需要判断相邻的两个数是否相等所以在一开始需要对nums进行排序。【排序和重复数字去重是一个配套操作需要一起来】
之后本题的和全排列的区别就在于需要判断相邻的两数是否相等并且前一个数是否没有用过。
for循环是横向遍历递归是纵向遍历即沿着树枝进行遍历的效果 used数组主要使用来记录哪些元素已经使用过了全排列问题中元素不能重复使用每个元素都只能适用一次。
class Solution:def permuteUnique(self, nums: List[int]) - List[List[int]]:res []def backtracking(path, used):if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):if i 0 and nums[i] nums[i - 1] and not used[i - 1]:continueif used[i]:continuepath.append(nums[i])used[i] Truebacktracking(path, used)path.pop()used[i] Falsenums.sort()backtracking([], [False] * len(nums))return res组合问题和排列问题是在树形结构的叶子结点上收集结果而子集问题就是取树上所有结点的结果。
and not used[i - 1]这部分代码是用来跳过重复的数字如果前一个数字没有被选取并且和当前数字值一致则可以跳过这部分这样的操作可以避免答案中出现重复的值。
使用uesd数组进行去重
class Solution:def permuteUnique(self, nums: List[int]) - List[List[int]]:res []used [False] * len(nums)def backtracking(path, used):if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):if i0 and nums[i]nums[i-1] and not used[i-1]:continueif used[i]:continueused[i] Truepath.append(nums[i])backtracking(path, used)used[i] Falsepath.pop()nums.sort()backtracking([], used)return res784、字母大小写全排列
322、重新安排行程hard) 51、N皇后 递归参数
定义res来存放最终的结果n棋盘大小row记录当前遍历到棋盘的第几层 递归终止条件 当递归到叶子结点的时候就可以收集结果了。
if rown:res.append(chessboard)return ;单层递归逻辑
遍历这个棋盘的每一行在python中二维数组的表示就用嵌套列表表示即可。
验证棋盘是否合法
皇后不能同行皇后不能同列皇后不能斜对角线45度和135度
def isValid(row, col, chessboard):# 列检查for i in range(row):if chessboard[i][col] Q:return False# 45°角检查 这里的检查是从row col往前找i,j row-1,col-1while i0 and j0:if chessboard[i][j] Q:return Falsei-1j-1# 135°角检查i,j row-1, col1while i0 and jlen(chessboard):if chessboard[i][j]Q:return Falsei - 1j 1return Trueclass Solution:def solveNQueens(self, n: int) - List[List[str]]: def backtracking(n,row,chessboard):# 递归终止的条件 当递归参数rown时就进行发返回 并将结果添加到res中if rown:res.append(chessboard[:])return# 对棋盘的每一行进行操作 判断是否合法for col in range(n):if isValid(row,col,chessboard):chessboard[row] chessboard[row][:col] Q chessboard[row][col1:]backtracking(n,row1,chessboard)chessboard[row] chessboard[row][:col] . chessboard[row][col1:]def isValid(row, col, chessboard):# 列检查for i in range(row):if chessboard[i][col] Q:return False# 45°角检查 这里的检查是从row col往前找i,j row-1,col-1while i0 and j0:if chessboard[i][j] Q:return Falsei-1j-1# 135°角检查i,j row-1, col1while i0 and jlen(chessboard):if chessboard[i][j]Q:return Falsei - 1j 1return Trueres []chessboard [.*n for _ in range(n) ]print(chessboard)backtracking(n,0,chessboard)return res解数独
回溯总结
需要startIndex的题目有
需要return的情况有
一般情况下如果题目中要求不能出现重复的数据需要搭配这used数组进行使用除此之外还需要对集合进行一个排序这样可以在值相同的情况下进行判断。
if i0 and nums[i]nums[i-1] and not used[i-1]:continueused[i-1]False 说明在同一层的前面结点已经使用过该数据了后面不需要重复进行操作。
如果集合中存在重复的数字序列则需要对其进行排序
组合总数II子集II全排列II
