仓储网站模板,太原网站搜索优化,中企动力企业邮箱手机登录入口,宁波企业自助建站系统目录
一、理论基础
二、例题
1. 排列问题
#xff08;1#xff09;无重复元素的排列问题
#xff08;2#xff09;有重复元素的排列问题
2. 组合问题
#xff08;1#xff09;无重复元素的组合问题
#xff08;2#xff09;无重复元素的子集问题
#xff08;…目录
一、理论基础
二、例题
1. 排列问题
1无重复元素的排列问题
2有重复元素的排列问题
2. 组合问题
1无重复元素的组合问题
2无重复元素的子集问题
3有重复元素的子集问题
4元素之和等于固定值
5非递减子序列问题
3. 括号生成
4. 电话号码数字组合
5. 分割回文字符 一、理论基础
回溯算法的基本理论还是递归思想所谓递归指的是函数在定义时调用函数本身且在函数定义中需要包含终止条件否则函数将无休止的调用自己直至内存不足。回溯算法是在递归思想的基础上制定的算法框架用于解决一类问题。这类问题的共性是问题本身可以被拆解为多个子问题每个子问题都是类似的选择题。算法框架如下
result []
def backtrace(选择列表nums, 路径pre_list):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:(有些问题需要对选择列表进行剪枝)做选择backtrace(剩余选择列表, 路径)撤销选择
每做出一个选择都是调用一次 backtrace 函数终止条件是用于终止该条路径的搜索选择列表是列出当前选择的所有可选项有可能此时需要根据情况进行剪枝。切记回溯算法本身其实是一种暴力遍历法并没有减少计算量它常用来解决不定数量的 for 循环嵌套问题。需要注意的是在 python 中result.add() 语句中需要深度拷贝“路径”原因是这个路径本身是一直在变化的。实现深度拷贝可以使用 copy 包可以使用 [:] 运算符列表转字符串时也是深拷贝。
二、例题
1. 排列问题
1无重复元素的排列问题
给定一个不含重复数字的数组 nums 返回其所有可能的全排列 。你可以按任意顺序返回答案。
示例
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
该问题最直观的想法是通过 n 个 for 循环迭代实现但是这样会造成同一个元素被重复使用。所以该问题可以看做是在一个长度为 n 的列表里填数据每填写一个数据都是做一个选择题每个选择题所面临的选项都是 n 个值但这个 n 的值需要加入剪枝以避免同一个元素被重复使用。注意 python 中的赋值、浅拷贝和深拷贝。
import copydef run1_1(nums):def backtracking(nums, result, path):if len(path) len(nums):result.append(copy.deepcopy(path))returnfor i in range(len(nums)):if nums[i] not in path:path.append(nums[i])backtracking(nums, result, path)path.pop()result []backtracking(nums, result, [])return result
2有重复元素的排列问题
给定一个可包含重复数字的序列 nums 按任意顺序返回所有不重复的全排列。
示例
输入nums [1,1,2]
输出[[1,1,2],[1,2,1],[2,1,1]]
该问题相比上一个问题相当于删除了一部分排列删除原因是这部分排列重复了原本 [位置1位置2] 与 [位置2位置1] 代表两个不同的排列现在位置1和位置2是相同元素所以变成同一个排列了。最直观的想法就是首先将 nums 排序然后在 for 循环中将相邻重复元素去除但是这样是错误的原因是这样做相当于去除了重复元素使得排列变短了。我们要做的是如果把所有的选择过程看成一个决策树那在同一层上不能选择两个相同的元素但是在不同层上是可以选择两个相同元素的。这样就保证了在选择的过程中同一个元素不能被重复使用但两个值相同的元素可以被重复使用。注意 对于长度为 2 的 numsnums[2] 会报错但是nums[2:]则不会报错。
import copydef run1_2(nums):def backtracking(nums, result, path):if not nums:result.append(copy.deepcopy(path))returnfor i in range(len(nums)):if i 0 or nums[i] ! nums[i-1]: # 保证同一层不出现重复元素path.append(nums[i])backtracking(nums[:i]nums[i1:], result, path) # 但是不同层会出现重复元素path.pop()result []nums.sort()backtracking(nums, result, [])return result
2. 组合问题
1无重复元素的组合问题
给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n 4, k 2
输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
该问题为组合问题同样可以看做是 k 次选择问题但是每次选择的选项需要基于前面的选择进行调整具体来说就是每个选择都要避免前面选择已经遍历过的选项。
import copydef run2_1(n, k):def backtracking(n, k, start, result, path):if len(path) k:result.append(copy.deepcopy(path))returnfor i in range(start, n):path.append(i)backtracking(n, k, i1, result, path)path.pop()result []backtracking(n, k, 0, result, [])return result
2无重复元素的子集问题
给你一个整数数组 nums 数组中的元素互不相同。返回该数组所有可能的子集幂集。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
该问题最直观的想法就是从 0 到 n 遍历所有长度然后针对每个长度调用上面的函数但是这样时间复杂度偏高还有更简单的方法在观察上面的回溯函数时发现其实每调用一次回溯函数都会生成一个子集。
import copydef run2_2(nums):def backtracking(nums, start, result, path):result.append(copy.deepcopy(path))for i in range(start, len(nums)):path.append(nums[i])backtracking(nums, i1, result, path)path.pop()result []backtracking(nums, 0, result, [])return result
3有重复元素的子集问题
给你一个整数数组 nums其中可能包含重复元素请你返回该数组所有可能的子集幂集。
解集不能包含重复的子集。返回的解集中子集可以按任意顺序排列。
示例
输入nums [1,2,2]
输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
该问题同样是需要避免在选择树的同一层选择两个相同的数值(避免两个[1,2])但是在不同层可以选择两个相同的数(必须包含[1,2,2]。其中start 参数解决了组合问题不设置终止条件解决了子集问题事先排序加 if i 0 or nums[i] ! nums[i-1] 解决了重复元素问题。
import copydef run2_3(nums):def backtracking(nums, start, result, path):result.append(copy.deepcopy(path))for i in range(start, len(nums)):if i 0 or nums[i] ! nums[i-1]:path.append(nums[i])backtracking(nums, i1, result, path)path.pop()result []nums.sort()backtracking(nums, 0, result, [])return result
4元素之和等于固定值
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明所有数字包括 target都是正整数。解集不能包含重复的组合。
示例
输入candidates [2,3,6,7], target 7,
所求解集为[[7],[2,2,3]]
该问题其实就是上面的无重复子集问题的扩展只是在寻找子集时还需要允许任意元素的重复使用此外在终止条件中还需要进行剪枝当某条搜索分支接下来不可能满足条件时及时终止对该分支的搜索。
import copydef run2_4(nums, n):def sum(path):n 0for i in path:n ireturn ndef backtracking(nums, start, result, path):if sum(path) n:result.append(copy.deepcopy(path))elif sum(path) n: # 终止对不满足条件分支的搜索returnfor i in range(start, len(nums)):path.append(nums[i])backtracking(nums, i, result, path) # 允许对某一元素的重复使用path.pop()result []backtracking(nums, 0, result, [])return result
5非递减子序列问题
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素 。你可以按任意顺序返回答案。数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
示例
输入nums [4,6,7,7]
输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
该问题看起来与有重复元素的子集问题极为相似都是遍历的每个路径都需要保存都是包含重复元素都是需要去除重复子集但是实际解法有些不同原因是该问题不能首先排序因为排序会打乱原有的顺序而本问题需要提取非递减序列。该问题是一个变长的回溯问题所以在回溯函数中每一步都需要保存不需要终止条件本题目要求序列长度大于等于 2所以需要增加一个 if 判断。该问题同样要保证不包含重复子集具体做法是保证在选择树的同一层里不能选择两个相同数值的数字但是在不同层可以选择这两个数字所以需要在遍历的 for 循环里面增加一个 if 判断这里是第二种实现方式第一种正如上面教程中是首先排序然后加入 if 判断。最后我为了保证所选择子集是非递减序列在选择数字时还需要增加一个 if 判断。
def run2_5(nums):def backtracking(result, path, nums, start):if len(path) 2: # 保证序列长度大于2result.append(path[:]) # 如果不使用[:] 则需要使用深拷贝函数copyfor i in range(start, len(nums)):if i start and nums[i] in nums[start:i]: # 保证当前层不使用相同数字不同层可以使用相同数字第二种实现方式第一种是首先排序然后加入if判断continueif not path or path[-1] nums[i]: # 保证非递减序列path.append(nums[i])backtracking(result, path, nums, i1)path.pop()result []backtracking(result, [], nums, 0)return result
3. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例
输入n 3
输出[((())),(()()),(())(),()(()),()()()]
该问题可以看做是需要做 2n 次选择每次选择都只有左括号和右括号两种选项但是左括号和右括号并不是同等地位的只有在还有未闭合的左括号时才可以加入右括号。此外还需要找到判断某字符串括号列表是否满足条件的判断条件判断条件是列表长度达到 2n且所有左括号都已闭合。判断所有左括号是否都已闭合的方法是用一个变量记录未闭合左括号的数量。
import copydef run3(n):def backtracking(n, count, result, path):# 判断括号字符串列表是否满足终止条件if len(path) 2*n:if count 0:result.append(copy.deepcopy(path))return# 首先选择左括号path (count 1backtracking(n, count, result, path)path path[:-1]count - 1# 在有未闭合左括号的前提下选择右括号if count 0:path )count - 1backtracking(n, count, result, path)path path[:-1]count 1result []backtracking(n, 0, result, )return result
4. 电话号码数字组合
在 9 宫格电话输入键盘中 2-9 数字分别对应着 3-4个字母给定一组数字输出所有可能的字母组合。
示例
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]
该问题最直观的想法就是使用 for 循环的嵌套例如上面示例使用两个 for 循环的嵌套即可生成最终结果但是该问题不能这样做的原因是数字字符串的长度不固定导致 for 循环的嵌套层数不固定无法实现最终编程。所以本问题采用回溯算法回溯函数的形参是当前翻译到哪个数字所以单次翻译中回溯函数被调用的次数等于数字字符串的长度除了数字 9 对应 4 个选择外其它数字都对应 3 个选择。
def run4(digits):if not digits:return list()phoneMap {2: abc,3: def,4: ghi,5: jkl,6: mno,7: pqrs,8: tuv,9: wxyz,}def backtrack(index: int):if index len(digits):combinations.append(.join(combination)) # 不需要深拷贝函数else:digit digits[index]for letter in phoneMap[digit]:combination.append(letter)backtrack(index 1)combination.pop()combination list()combinations list()backtrack(0)return combinations
5. 分割回文字符串
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串 。返回 s 所有可能的分割方案。回文串是正着读和反着读都一样的字符串。
示例
输入s aab
输出[[a,a,b],[aa,b]]
本问题看起来需要两步完成第一步是切割字符串第二步是判断字符串是否为回文字符串。第一步的切割字符串这个问题看起来与子集问题很相似但实际并不是子集问题不用管字符串整体分割的完整性本问题需要考虑完整性即需要将整个字符串完整分割。每次分割都可以看做一个选择所以本问题依然是不定数量的选择问题所以本问题用回溯来实现分割但与之前回溯不一样的是本问题在调用回溯函数时需要完成两个数值的选择之前的应用都是仅仅完成一个数值的选择(其实本质上没有区别)。回溯函数的形参是每个选择或者分割的起始位置函数体内完成的是本次选择或分割的终止位置的选择。回溯的终止条件肯定是当分割的起始位置超过字符串的总长时终止迭代。以此完成了字符串的分割下一步是判断每个字符串是否为回文字符串如果每个字符串都计算一次很显然存在重复计算所以这里使用动态规划缩减计算量。具体来说是定义一个二维的矩阵 dp(i, j)行 i 是起始位置列 j 是终止位置迭代条件很明显是如果 s[i] s[j]且 dp[i1, j-1] 为 true则 dp[i, j] 为 true为了解决 i j 时的递推初始化时整个矩阵初始化为 true。从递推公式中可以发现 dp[i, j] 依赖于 dp[i1, j-1]所以递推顺序可以为 i 递减 j 递增。
def run5(s):# 动态规划部分n len(s)f [[True] * n for _ in range(n)]for i in range(n - 1, -1, -1):for j in range(i 1, n):f[i][j] (s[i] s[j]) and f[i 1][j - 1]# 回溯部分ret list()ans list()def dfs(i: int):if i n:ret.append(ans[:]) # 不需要深拷贝函数returnfor j in range(i, n):if f[i][j]:ans.append(s[i:j1])dfs(j 1)ans.pop()dfs(0)return ret
