回溯算法解决组合排列问题

2024-08-29 20:04
文章标签 算法 问题 组合 解决 排列 回溯

本文主要是介绍回溯算法解决组合排列问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先，组合问题和子集问题其实是等价的，这个后面会讲；至于之前说的三种变化形式，无非是在这两棵树上剪掉或者增加一些树枝罢了

我们通过保证元素之间的相对顺序不变来防止出现重复的子集。

如果把根节点作为第 0 层，将每个节点和根节点之间树枝上的元素作为该节点的值，那么第 n 层的所有节点就是大小为 n 的所有子集。

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：

def backtrack(...):for 选择 in 选择列表:做选择backtrack(...)撤销选择

写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

78. 子集

class Solution:def __init__(self):self.res = []def subsets(self, nums: List[int]) -> List[List[int]]:track = [] #回溯问题的track多使用局部变量来表达，再通过回溯函数传递，局部变量具有临时使用的特性，不是一直使用self.backtrack(nums, 0, track) return self.res def backtrack(self, nums, start, track) :self.res.append(track[:]) #初始为空，for i in range(start, len(nums)):#这里的nums就是选择列表track.append(nums[i])self.backtrack(nums, i + 1, track)track.pop()

77. 组合

class Solution:def __init__(self):self.res = []# 记录回溯算法的递归路径self.track = []# 主函数def combine(self, n: int, k: int) -> List[List[int]]:self.backtrack(1, n, k)#k>=1 ， 所以这里start可以从1开始return self.resdef backtrack(self, start: int, n: int, k: int) -> None:# base caseif k == len(self.track):# 遍历到了第 k 层，收集当前节点的值self.res.append(self.track.copy())return# 回溯算法标准框架for i in range(start, n+1):# 选择self.track.append(i)# 通过 start 参数控制树枝的遍历，避免产生重复的子集self.backtrack(i + 1, n, k)# 撤销选择self.track.pop()

组合问题可以由子集问题容易得到，取第k层就可以获得大小为k的组合。

刚才讲的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。

但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择 排列问题本来就是在玩转位置

递归就像你遇到一个任务，它的解决方法是去完成一个规模更小但相似的任务，而那个小任务的解决方法又是去完成另一个更小的任务，直到任务小到你可以轻松完成为止。在编程中，这种技术通过函数自我调用来实现，用于解决可以分解成子问题的问题。

90. 子集 II

class Solution:def __init__(self):self.res = []self.track = []def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:# 先排序，让相同的元素靠在一起nums.sort()self.backtrack(nums, 0)return self.resdef backtrack(self, nums: List[int], start: int) -> None:# 前序位置，每个节点的值都是一个子集self.res.append(self.track[:])for i in range(start, len(nums)):# 剪枝逻辑，值相同的相邻树枝，只遍历第一条if i > start and nums[i] == nums[i - 1]:continueself.track.append(nums[i])self.backtrack(nums, i + 1)self.track.pop()

两条值相同的相邻树枝会产生重复 ，进行剪枝操作，

剪枝（Pruning）是一种在算法（尤其是回溯算法）中使用的优化技术。它的核心思想是在搜索问题解空间时，提前终止那些不会产生有效解或不必要的搜索路径，从而减少计算量，提高算法效率。

什么是剪枝操作

在许多组合问题中，解空间（所有可能的解组合）可能非常庞大，而其中只有一部分是有效的或符合要求的解。剪枝的目的是在搜索的过程中，识别并跳过那些不可能产生有效解的分支。

例如，在回溯算法中，每次选择一个选项（即进入一个分支），再继续尝试下一个选项。但在某些情况下，你可以通过提前判断，发现某个分支已经不能满足条件，那么就可以直接放弃这个分支的进一步探索，这就是剪枝。

为什么要剪枝

  1. 减少计算量：剪枝可以大幅度减少需要计算的分支，从而减少整个问题的搜索空间。例如，在求解一个复杂的组合问题时，如果不剪枝，算法可能需要遍历所有可能的组合。但通过剪枝，可以跳过不可能的分支，减少遍历的次数。
  2. 提高效率：剪枝可以显著提高算法的运行效率，使得原本可能无法在合理时间内完成的计算变得可行。在一些实际应用中，剪枝往往是使问题从“无法解决”变为“可以解决”的关键。
  3. 避免冗余计算：剪枝还能帮助避免重复计算不必要的分支。例如，在某些问题中，某些路径可能会多次出现，通过剪枝可以避免这些重复的计算。

总结

剪枝操作通过智能地减少算法的搜索空间，显著提升了算法的效率和执行速度。在处理组合问题、搜索问题时，剪枝往往是不可或缺的优化手段。它的核心思想就是“减少不必要的工作”，通过跳过不可能成功的路径来节省时间和资源。

  • 作用范围：
    • continue 仅影响循环内部，它会跳过当前迭代的剩余部分，但循环仍继续执行下一次迭代。
    • return 直接终止整个函数的执行，并且函数返回到调用者处，不再执行任何代码。
  • 使用位置：
    • continue 只能用于循环中（如 for 和 while）。
    • return 只能用于函数内部，用来结束函数并返回值。
  • 执行流程影响：
    • continue 只是跳过循环中的部分代码，不会终止循环本身。
    • return 则完全终止函数的执行，并返回到函数的调用点。

总结

  • continue 是一个跳过当前循环迭代剩余部分的指令，让循环继续下一个迭代。
  • return 则是一个结束函数执行的指令，通常用于函数的结果返回，并退出函数。

两者在控制程序执行流程时，作用域和效果截然不同。

也就是continue是在循环时候使用， return是在函数结束递归的时候使用。!!!基础知识点

组合问题和子集问题是等价的， 剪枝操作！！第一次接触

40. 组合总和 II

class Solution:def __init__(self):self.res = []# 记录回溯的路径self.track = []# 记录 track 中的元素之和self.trackSum = 0def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:# 先排序，让相同的元素靠在一起candidates.sort()self.backtrack(candidates, 0, target)return self.res# 回溯算法主函数def backtrack(self, nums: List[int], start: int, target: int):# base case，达到目标和，找到符合条件的组合if self.trackSum == target:self.res.append(self.track[:])return#return代表这一层递归结束# base case，超过目标和，直接结束 #也是剪纸的一部分if self.trackSum > target:return# 回溯算法标准框架for i in range(start, len(nums)):# 剪枝逻辑，值相同的树枝，只遍历第一条 #减去旁边值相同的数值，不然会造成重复使用if i > start and nums[i] == nums[i - 1]: #减去数枝continue#continue只是这一层循环结束# 做选择self.track.append(nums[i])self.trackSum += nums[i]# 递归遍历下一层回溯树self.backtrack(nums, i + 1, target)# 撤销选择self.track.pop()self.trackSum -= nums[i]

47. 全排列 II

class Solution:def __init__(self):self.track = []self.res = []self.used = []def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()#加一下排序，后序进行剪纸self.used = [False] * len(nums)self.backtrack( nums) return self.res def backtrack(self, nums) -> None:if len(self.track) == len(nums):self.res.append(self.track[:])return #这里加return结束递归for i in range(0, len(nums)):if self.used[i]:continue #这是排列问题，这个元素用过就不能再排列了if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:continue self.track.append(nums[i])self.used[i] = True self.backtrack(nums)self.track.pop()self.used[i] = False

此剪枝思路，保证了2,2’,2’'的相对位置，去除了重复。

保证相同元素在排列中的相对位置保持不变。 标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。 当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

子集问题和组合问题是同一类问题 标准的子集，组合问题，通过控制start来控制无重复问题， 排列问题通过used来控制位置。

# 无重组合的回溯算法框架
def backtrack(nums: List[int], start: int) -> None:for i in range(start, len(nums)):# ...# 递归遍历下一层回溯树，注意参数backtrack(nums, i + 1)# ...

想让每个元素被重复使用，我只要把 i + 1 改成 i 即可：

# 可重组合的回溯算法框架
def backtrack(nums: List[int], start: int):for i in range(start, len(nums)):# ...# 递归遍历下一层回溯树，注意参数backtrack(nums, i)# ...

当然，这样这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的 base case 以结束算法

类变量:

  • 类变量是在类的定义中声明的变量，不属于任何特定的实例。所有该类的实例共享同一个类变量的值。
  • 在Python中，类变量通常在类体内（但在任何方法之外）定义。它们由类的所有实例共享，这意味着如果一个实例修改了类变量的值，那么这个修改对所有实例都可见。

实例变量:

  • 实例变量是在类的实例（对象）中声明的变量。每个实例都有自己独立的实例变量，互不干扰。
  • 在Python中，实例变量通常在 __init__ 方法中使用 self 关键字进行声明，并且只属于特定的实例。
class Solution:def __init__(self):self.res = []def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.backtrack(candidates, 0, target, 0) #sum一开始是0return self.res track = []#这里的track是类变量，写在init里面写成类变量也可以def backtrack(self, candidates: List, start:int, target: int, sum: int) -> None:if sum == target:self.res.append(self.track.copy())return if sum > target:return for i in range(start, len(candidates)):self.track.append(candidates[i])sum += candidates[i]self.backtrack(candidates, i, target, sum)sum -= candidates[i]self.track.pop()

总结

  • 类变量: 用于共享属性或方法，适合类的所有实例共享的值。
  • 实例变量: 用于保存对象的状态，适合每个实例独立维护的值。
  • 局部变量: 用于函数或方法的临时计算，适合只在函数或方法内部使用的值。

总结：

形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：

# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):# 回溯算法标准框架for i in range(start, len(nums)):# 做选择track.append(nums[i])# 注意参数backtrack(nums, i + 1)# 撤销选择track.pop()# 排列问题回溯算法框架
def backtrack(nums: List[int]):for i in range(len(nums)):# 剪枝逻辑if used[i]:continue# 做选择used[i] = Truetrack.append(nums[i])backtrack(nums)# 撤销选择track.pop()used[i] = False

形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下： 跳出重复元素

nums.sort()
# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):# 回溯算法标准框架for i in range(start, len(nums)):# 剪枝逻辑，跳过值相同的相邻树枝if i > start and nums[i] == nums[i - 1]:continue# 做选择track.append(nums[i])# 注意参数backtrack(nums, i + 1)# 撤销选择track.pop()nums.sort()
# 排列问题回溯算法框架
def backtrack(nums: List[int]):for i in range(len(nums)):# 剪枝逻辑if used[i]:continue# 剪枝逻辑，固定相同的元素在排列中的相对位置if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continue# 做选择used[i] = Truetrack.append(nums[i])backtrack(nums)# 撤销选择track.pop()used[i] = False

形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：

# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):# 回溯算法标准框架for i in range(start, len(nums)):# 做选择track.append(nums[i])# 注意参数backtrack(nums, i)# 撤销选择track.pop()# 排列问题回溯算法框架
def backtrack(nums: List[int]):for i in range(len(nums)):# 做选择track.append(nums[i])backtrack(nums)# 撤销选择track.pop()

这篇关于回溯算法解决组合排列问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1118756。

相关文章

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

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

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

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

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算法中会用到）

康拓展开（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]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

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

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu4869（逆元+求组合数）

hdu4869（逆元+求组合数）

//输入n，m，n表示翻牌的次数，m表示牌的数目，求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
如何解决线上平台抽佣高 线下门店客流少的痛点！

如何解决线上平台抽佣高 线下门店客流少的痛点！

目前，许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流，但其费用昂贵。鉴于此，众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台，但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下，商家之间的合作网络逐渐成为一种有效的解决方案，通过资源和客户基础的共享，实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例，该平台融合了环保消费积分系统，在短
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2