当前位置：首页 > news >正文

课程讲解---深搜

news 2024/12/28 17:03:47

点个赞再看吧(#^.^#)

深搜时间复杂度：

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。其时间复杂度取决于具体的应用场景和数据结构。

对于图：
- 如果使用邻接矩阵表示图，DFS的时间复杂度为 O(V^2)，其中 V 是顶点的数量。这是因为每个顶点都可能与其他所有顶点相连。
- 如果使用邻接表表示图，DFS的时间复杂度为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。这是因为每个顶点和每条边都会被访问一次。
对于树：
- 在树的情况下，DFS的时间复杂度为 O(V)，其中 VV 是节点的数量。因为树是一种特殊的图，没有环且边数 EE 等于 V - 1。

需要注意的是，DFS的空间复杂度通常为 O(V)，因为在最坏情况下，递归调用栈会包含所有的顶点。

总结：

对于邻接矩阵表示的图，DFS的时间复杂度为 O(V^2)。
对于邻接表表示的图，DFS的时间复杂度为 O(V + E)。
对于树，DFS的时间复杂度为 O(V)。

深搜的注意事项

深度优先搜索（深搜）的基本概念和原理

深度优先搜索（Depth First Search，简称DFS）是图遍历算法的一种。它的基本原理可以用一句话概括为“一直往下走，走不通回头，换条路再走，直到无路可走”。

具体来说，深搜会选择一个起始点作为当前结点。首先访问这个当前结点，并且标记该结点已被访问。然后检查是否存在一个和当前结点相邻并且尚未被访问的结点，如果存在这样的结点，就将其设为新的当前结点，然后重复前面的操作；如果不存在这样的结点，就进行回溯，也就是回退当前结点。

例如在一个迷宫中寻找出口，深搜从入口开始，沿着一条路一直走下去，直到遇到死胡同或者已经到达过的位置，然后再返回上一个岔路口，选择另一条未走过的路继续探索，如此反复，直到找到出口或者确定迷宫没有出口为止。在这个过程中，深搜像是一个执着探索的行者，不轻易改变方向，只有在当前路径无法继续时才会考虑其他路径。

深搜还可以通过递归或者使用栈来实现。递归方式的代码相对简洁，其本质就是函数自己调用自己来实现不断深入探索的过程。例如在对树形结构进行深搜时，递归可以很好地体现从根节点到叶子节点的深度优先遍历过程。使用栈来实现时，每次访问到的结点入栈，回溯的时候出栈，栈顶元素始终表示当前正在探索的节点。

深搜常见错误及解决方法

（一）运行超时

1. 错误表现

在处理一些情况比较复杂、数据量较大的问题时，深搜由于其时间复杂度较高，可能会导致程序运行时间过长，甚至出现运行超时的情况。这是因为深搜会穷举所有可能的情况，如果问题规模庞大，计算量会呈指数级增长。

2. 解决方法

剪枝操作：
- 可行性剪枝：在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。例如在计算数的组合问题中，如果当前组合的和已经超过了目标值，那么这个分支就无需继续探索，可以直接回溯。这种剪枝方式就像在搜索过程中提前排除那些明显不符合要求的路径，减少不必要的搜索。
- 最优化剪枝：如果已经找到一个可行解，并且在后续搜索中发现某个分支不可能产生更优的解，那么就可以停止对这个分支的搜索。比如在寻找图中最短路径问题时，如果已经找到一条长度为5的路径，当探索到某个分支时发现这个分支后续的路径长度必然大于5，就可以放弃这个分支的搜索。
优化搜索顺序：
- 在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。通过合理安排搜索顺序，可以使搜索树的规模更小，从而减少搜索时间。例如在全排列问题中，按照字典序进行搜索可以避免一些重复的搜索过程。
排除等效冗余：
- 在搜索过程中，如果能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。例如在一个对称的图结构中，对称的分支可能会产生相同的搜索结果，这时就可以只搜索其中一条分支，从而减少搜索量。

（二）栈溢出（针对递归实现的深搜）

1. 错误表现

当深搜的递归层数过深时，可能会导致栈溢出。因为每次递归调用都会在栈中占用一定的空间，如果递归调用的次数过多，超出了栈的容量，就会发生栈溢出错误。这种情况在处理大规模数据或者复杂结构的深搜时比较容易出现。

2. 解决方法

调整算法结构：
- 如果可能的话，将递归实现的深搜改为非递归实现，通过使用栈数据结构来模拟递归过程。这样可以更灵活地控制栈的大小，避免栈溢出。例如在遍历二叉树时，可以使用一个显式的栈来存储待访问的节点，而不是依赖于系统的递归调用栈。
优化搜索策略：
- 采用剪枝等优化技巧减少不必要的递归调用。如果能够提前判断某些情况不需要继续递归探索，就可以避免进入更深层次的递归，从而减少栈的使用量。

（三）忽略标记已访问节点

1. 错误表现

在深搜过程中，如果忘记标记已经访问过的节点，可能会导致程序陷入无限循环。例如在图的遍历中，可能会不断地在已经访问过的节点之间循环访问，无法继续探索新的节点，也无法完成整个图的遍历。

2. 解决方法

在访问每个节点后，及时将其标记为已访问状态。可以使用一个数组或者哈希表等数据结构来记录节点的访问状态，根据具体的问题和数据结构选择合适的标记方式。在后续搜索过程中，遇到已标记为已访问的节点时，就不再对其进行重复访问。

深搜的优化技巧

（一）剪枝技术

1. 可行性剪枝

可行性剪枝是深搜优化中常用的一种手段。在搜索过程中，不断检查当前状态是否满足问题的约束条件，如果不满足，就直接停止对当前分支的搜索，回溯到上一层。例如，在解决数独问题时，如果在某个格子中填入一个数字后，发现会导致同一行、同一列或者同一个九宫格内出现重复数字，那么这个数字的选择就是不可行的，就可以直接回溯，尝试其他数字。
这种剪枝方式可以有效地减少搜索空间，避免在不可能得到解的分支上浪费时间。其关键在于根据问题的特点，准确地定义和判断不可行的状态。

2. 最优化剪枝

当搜索目标是寻找最优解时，最优化剪枝非常有效。假设我们正在寻找图中从起点到终点的最短路径，在深搜过程中，如果已经找到了一条长度为L的路径，那么对于后续搜索中遇到的某个分支，如果从该分支继续搜索得到的路径长度必然大于L，就可以停止对这个分支的搜索。因为这个分支不可能产生更优的解。
最优化剪枝需要在搜索过程中动态地维护当前的最优解，并根据这个最优解来判断后续分支是否有继续搜索的必要。这要求在设计算法时，能够合理地记录和更新最优解的值。

3. 记忆化搜索（Memoization）

记忆化搜索也是一种特殊的剪枝技巧。它主要用于解决有重叠子问题的搜索问题。例如，在计算斐波那契数列时，如果直接使用深搜，会存在大量的重复计算。通过使用记忆化搜索，我们可以创建一个数组来存储已经计算过的结果，当再次需要计算相同的子问题时，直接从数组中获取结果，而不需要重新计算。
这种方法可以大大提高搜索效率，尤其是对于那些子问题重复度较高的问题。在实际应用中，需要根据问题的结构确定哪些子问题需要进行记忆化，以及如何存储和获取这些记忆化的结果。

（二）迭代加深

迭代加深是深搜和广搜的一种结合方式。普通深搜求最优解必须遍历所有状态打擂台得到，而迭代加深后，第一次遇见目标状态即可得到最优解。它的基本思想是不断放宽迭代深度限制，第一次找到的目标状态即为最优解。
例如在一个搜索树中，如果直接使用深搜可能会陷入很深的分支而无法快速找到最优解。通过迭代加深，我们可以先限制搜索深度为1，进行一次深搜，如果没有找到目标，再将搜索深度增加到2，继续进行深搜，以此类推。这样可以在一定程度上避免深搜陷入过深的无用分支，同时又能够利用深搜深入探索的特性。

（三）优化搜索顺序

在搜索问题中，不同的搜索顺序会产生不同规模的搜索树。例如在全排列问题中，如果按照字典序进行搜索，会使搜索树的结构更加有序，减少不必要的搜索。假设我们要对数字1、2、3进行全排列，按照字典序从123开始搜索，会比随机搜索更加高效。
通过分析问题的特点，找到一种合理的搜索顺序，可以有效地减少搜索空间。这可能需要对问题有深入的理解，例如在某些图的搜索问题中，根据节点的度数、与目标节点的距离等因素来确定搜索顺序，可以提高搜索效率。

（四）排除等效冗余

在搜索树中，如果从当前节点出发，沿着不同分支到达的子树是等效的，那么只需要搜索其中一个分支即可。例如在一个对称的迷宫中，对称的路径可能会导致相同的搜索结果。如果我们能够识别出这种等效性，就可以只搜索其中一条对称路径，从而减少搜索量。
要实现排除等效冗余，需要对问题的结构和性质有清晰的认识，能够准确地判断哪些分支是等效的。这可能需要根据具体问题的数学模型或者几何特征来进行分析。

深搜在不同场景中的应用注意事项

（一）路径搜索问题

1. 迷宫问题

在迷宫问题中应用深搜时，需要注意迷宫的边界条件。确保搜索过程中不会越界访问迷宫数组。例如，如果迷宫是一个二维数组表示的，在访问上下左右相邻的格子时，要检查坐标是否在合法范围内。
同时，要注意标记已经访问过的格子，以避免在迷宫中陷入循环。如果不标记已访问的格子，可能会一直在一个小区域内打转，无法找到出口。
另外，在寻找从起点到终点的路径时，可能存在多条路径，深搜通常会找到其中一条路径。如果需要找到最短路径，可能需要对深搜进行优化，或者考虑使用广度优先搜索（BFS），因为BFS更适合寻找最短路径问题。

2. 图中的路径查找

在图中进行路径搜索时，要考虑图的连通性。如果图是不连通的，可能需要对每个连通分量分别进行深搜。
对于有向图和无向图，深搜的策略可能需要有所调整。在无向图中，相邻节点的关系是双向的，而在有向图中，需要按照边的方向进行搜索。
还需要注意图中可能存在的环。如果不加以处理，深搜可能会在环中无限循环。可以通过标记已访问节点来避免陷入环中。

（二）全排列问题

在全排列问题中，要确保每个元素在每个排列中只出现一次。可以通过标记已经使用过的元素来实现。例如，使用一个布尔数组来标记每个元素是否已经被放入排列中。
深搜的终止条件是当排列中的元素个数等于原始集合中的元素个数时，表示已经得到一个全排列。在实现过程中，要准确地判断这个终止条件，避免过早或过晚终止搜索。
另外，由于全排列的数量可能非常庞大，当元素个数较多时，可能会面临时间和空间复杂度的挑战。可以使用优化技巧，如优化搜索顺序等，来减少搜索空间和计算时间。

（三）数塔问题

在数塔问题中，深搜通常用于寻找从塔顶到塔底的最大（小）和路径。在搜索过程中，要注意每个节点只能选择其下一层相邻的节点进行路径延伸。
为了避免重复计算，可以使用记忆化搜索。因为从不同的上层节点到达同一个下层节点可能会有多次计算，通过记忆化可以提高效率。
当数塔规模较大时，深搜的时间复杂度可能较高，需要考虑剪枝等优化手段。例如，如果已经发现某条路径的和明显小于当前找到的最大和路径，就可以停止对这个分支的搜索。

深搜与其他搜索算法的比较

（一）与广度优先搜索（BFS）的比较

1. 搜索策略

深搜（DFS）：深搜是深入其中、直取结果的搜索方法。它从一个起始点出发，沿着一条路径尽可能深地探索下去，直到无法继续，然后回溯到上一个未完全探索的节点，再选择另一条路径继续探索。就像一个人在迷宫中只沿着一条路走到底，走不通再回头换路一样。这种搜索方式可能会在搜索树的一个分支上深入很多层，然后才返回去探索其他分支。
广度优先搜索（BFS）：BFS则是一层一层地进行搜索，从起始点开始，先探索起始点的所有邻居节点，然后再依次探索这些邻居节点的邻居节点，以此类推。可以想象成以起始点为中心，向外逐层扩展搜索范围，就像水波一样扩散开来。例如在一个分层结构的图中，BFS会先搜索同一层的所有节点，然后再进入下一层搜索。

2. 适用场景

深搜（DFS）：
- 深搜一般用于求可行解，例如在迷宫中寻找是否存在从入口到出口的路径，只要找到一条路径就可以停止搜索。在树形结构的图上用处较多，因为树形结构天然适合深搜的深度优先遍历方式。在全排列、组合等问题中，深搜可以通过递归的方式方便地枚举所有可能的情况。
- 但是，深搜在搜索过程中可能会陷入很深的递归层次，如果搜索树很深且没有优化，可能会导致栈溢出或者效率低下。而且，深搜不适合直接用于寻找最优解，因为它需要遍历完所有可能的解才能确定最优解（除非使用特殊的优化技巧，如迭代加深）。
广度优先搜索（BFS）：
- BFS一般用于求最优解，特别是在寻找最短路径问题上表现出色。因为BFS是按照层次进行搜索的，当找到目标节点时，所经过的路径就是最短路径（在边权值都相同的情况下）。例如在地图上寻找两个地点之间的最短距离，使用BFS可以快速得到结果。
- 不过，BFS需要使用队列来存储待访问的节点，当搜索空间很大时，队列可能会占用大量的内存空间。而且BFS的搜索效率在某些情况下可能不如深搜，例如在树形结构中，如果树的深度很大且宽度很小，BFS可能会搜索很多不必要的节点。

3. 实现方式

深搜（DFS）：深搜的实现方式主要有递归和使用栈两种。递归方式代码简洁，逻辑清晰，适合初学者理解深搜的原理。但是递归可能会导致栈溢出的问题，尤其是在搜索树很深的情况下。使用栈来实现深搜可以避免递归带来的栈溢出风险，通过手动模拟栈的操作，可以更灵活地控制搜索过程，但代码相对复杂一些。
广度优先搜索（BFS）：BFS主要通过队列来实现。将起始节点入队，然后不断取出队首节点，将其未访问过的邻居节点入队，直到队列为空或者找到目标节点。这种实现方式利用了队列先进先出的特性，保证了搜索按照层次进行。

（二）与其他搜索算法的比较

1. 与A*搜索算法的比较

深搜（DFS）：
- DFS是一种盲目搜索算法，它在搜索过程中没有利用任何关于目标位置的启发式信息，只是按照预定的规则进行搜索。这使得它在搜索空间较大时可能会搜索很多不必要的路径。
- 深搜的时间复杂度通常较高，尤其是在没有优化的情况下，可能会遍历整个搜索空间。例如在一个复杂的游戏地图中寻找特定目标，如果使用深搜，可能会在很多无关的区域浪费大量时间。
A*搜索算法：
- A搜索算法是一种启发式搜索算法，它在搜索过程中会根据一个评估函数来选择下一个要搜索的节点。这个评估函数综合考虑了从起始点到当前节点的实际代价和从当前节点到目标点的估计代价。通过这种方式，A算法可以更有针对性地朝着目标方向进行搜索，减少不必要的搜索。
- A算法在寻找最优解方面通常比深搜更高效，尤其是在搜索空间较大且有一定的启发式信息可以利用的情况下。例如在路径规划问题中，如果知道目标点的大致方向，A算法可以更快地找到从起始点到目标点的最短路径。

2. 与二分搜索算法的比较

深搜（DFS）：
- DFS主要用于图和树等复杂数据结构的搜索，其搜索空间是离散的、不规则的。深搜的搜索过程是深度优先的，可能会遍历整个图或者树的大部分节点来找到目标。
- 深搜的时间复杂度取决于搜索空间的大小和结构，在最坏情况下可能是指数级的。例如在一个完全二叉树中进行深搜，最坏情况下需要遍历所有的叶子节点，节点数量随着树的深度呈指数增长。
二分搜索算法：
- 二分搜索算法主要用于有序数组等线性数据结构的搜索。它的基本思想是将搜索区间不断缩小一半，直到找到目标元素或者确定目标元素不存在。二分搜索算法的时间复杂度是对数级的，效率非常高。
- 二分搜索算法要求搜索的数据结构必须是有序的，并且每次比较都能将搜索区间缩小一半。这与深搜的应用场景有很大的区别，深搜不需要数据结构是有序的，而且搜索方式也完全不同。

深搜数组全排列和

深搜数组全排列的基本概念

全排列是组合数学中的一个重要概念。从n个不同元素中取出m个元素（m≤n），按照一定的顺序排成一列的所有可能的排列方式，就叫做从n个不同元素中取出m个元素的排列。当m = n时，这就是全排列，也就是将这n个元素的所有可能的排列情况都列出来。例如，对于数字1、2、3，全排列就是123、132、213、231、312、321这六种情况。

在深度优先搜索（DFS）解决数组全排列问题时，我们可以将其看作是一个排列树的遍历问题。树的每个节点代表一个部分排列，从根节点到叶节点的路径则代表一个完整的排列。比如对于一个数组 [1, 2, 3]，我们从根节点开始，第一个选择有3种（1、2或者3），假设选择了1，那么下一层节点对于剩下的2和3又有不同的选择情况，这样不断深入直到形成一个完整的排列，就像在一棵树上从根到叶子的遍历过程。这其中的每一条从根到叶的路径就是一个全排列结果。深度优先搜索通过递归或者栈的方式，不断深入到树的底层，再回溯到上层节点去探索其他可能的分支，从而找出所有的全排列情况。这种方式可以系统地遍历所有可能的排列组合，确保不遗漏任何一种全排列情况。

深搜数组全排列的实现方法

深度优先搜索实现数组全排列主要有以下方法：

递归实现
- 基本思路：首先确定递归的终止条件，通常是当已经处理完数组中的所有元素时，表示已经得到一个全排列。然后在每一层递归中，遍历数组中的每个元素，对于未被使用过的元素，将其加入到当前的排列中，并标记为已使用，然后递归进入下一层处理下一个位置的元素。当回溯时，要将该元素的使用标记清除，以便在其他分支中可以再次使用。
- 举例：假设要对数组 [1, 2, 3] 进行全排列。在第一层递归中，先选择1，标记1已使用，然后进入第二层递归。在第二层递归中，从剩下的2和3中选择，假设选择2，标记2已使用，再进入第三层递归，此时只剩下3，将3加入得到 [1, 2, 3] 这个全排列。然后回溯到第二层递归，将2的使用标记清除，再选择3，得到 [1, 3, 2]。之后回溯到第一层递归，清除1的使用标记，重新选择2，重复上述过程。
利用栈实现（非递归方式）
- 基本思路：使用一个栈来模拟递归的过程。首先将初始状态（如空的排列和未处理的数组）压入栈中。然后在循环中不断取出栈顶元素，如果栈顶元素代表的状态还未完成全排列（即排列中的元素个数小于数组元素个数），则从数组中选择未被使用的元素加入到排列中，并将新状态压入栈中。如果已经完成全排列，则将该全排列结果记录下来，并回溯到上一个状态。
- 对比递归方式：递归方式相对简洁直观，容易理解，代码实现较为紧凑，但是在处理大规模数据时可能会导致栈溢出，因为递归调用需要消耗系统栈空间。非递归方式利用栈来手动模拟递归过程，相对来说对栈的使用更加可控，可以避免一些递归可能带来的问题，如栈溢出，但代码的逻辑相对复杂一些，需要更多的手动状态管理。

深搜数组全排列的代码示例

以下是一个使用递归实现深度优先搜索数组全排列的C++ 代码示例：

#include <iostream>
#include <vector>// 用于标记数组中的元素是否已被使用
std::vector<bool> used; 
// 存储当前排列
std::vector<int> current_permutation; 
// 存储所有全排列结果
std::vector<std::vector<int>> all_permutations; // 深度优先搜索函数
void dfs(const std::vector<int>& nums) {// 递归终止条件：当当前排列的元素个数等于原数组个数时，表示得到一个全排列if (current_permutation.size()  == nums.size())  {all_permutations.push_back(current_permutation);  return; }for (size_t i = 0; i < nums.size();  ++i) {if (!used[i]) {// 将未使用的元素加入当前排列current_permutation.push_back(nums[i]);  used[i] = true; // 递归进入下一层dfs(nums); // 回溯：将元素从当前排列中移除，并标记为未使用current_permutation.pop_back();  used[i] = false; }}
}std::vector<std::vector<int>> permute(const std::vector<int>& nums) {used = std::vector<bool>(nums.size(),  false); dfs(nums); return all_permutations; 
}

在这个代码中：

used 数组用于标记 nums 数组中的元素是否已经被使用过。
current_permutation 用于存储正在构建的全排列。
all_permutations 用于存储最终得到的所有全排列结果。
dfs 函数是核心的深度优先搜索函数，它按照上述的递归思路构建全排列。首先判断是否达到递归终止条件，如果是则将当前排列加入结果集。然后遍历原数组，对于未被使用的元素，加入当前排列，标记为已使用，递归下一层，最后回溯。
permute 函数用于初始化相关变量，并调用 dfs 函数，最后返回所有全排列结果。

深搜数组全排列的优化技巧

剪枝策略
- 重复元素的处理：如果数组中存在重复元素，在进行全排列搜索时会产生大量重复的结果。为了避免这种情况，可以在搜索之前对数组进行排序，然后在选择元素时，如果当前元素与前一个元素相同且前一个元素还未被使用，就跳过当前元素的选择。例如，对于数组 [1, 2, 2]，在处理第二个2时，如果第一个2还未被使用，那么这个第二个2产生的排列情况必然会与第一个2产生的重复，所以可以直接跳过。这样可以大大减少搜索的分支数量，提高效率。
- 基于排列顺序的剪枝：在某些情况下，可以根据全排列的字典序等特定顺序要求进行剪枝。例如，如果已经找到的全排列按照字典序已经大于目标全排列（如果有目标全排列的情况），那么就可以停止搜索。
状态压缩：在记录元素是否被使用的状态时，可以采用更紧凑的方式。例如，如果数组中的元素值范围较小，可以使用一个整数的二进制位来表示元素的使用状态，而不是使用一个布尔数组。这样可以减少内存的占用，提高程序的运行效率。
记忆化搜索：如果在全排列的搜索过程中存在大量重复的子问题，可以采用记忆化搜索的方式。例如，在计算某个子排列的后续全排列情况时，如果之前已经计算过相同子排列的情况，就可以直接使用之前的结果，而不需要再次进行搜索。这可以避免重复计算，提高搜索效率。

深搜数组全排列的应用场景

组合优化问题
- 旅行商问题（TSP）：旅行商需要访问一系列城市并回到起始城市，目标是找到最短的旅行路线。可以将城市看作是数组中的元素，全排列表示不同的旅行路线顺序。通过深度优先搜索数组全排列，可以列举出所有可能的旅行路线，然后计算每条路线的总距离，从而找到最短距离的路线。例如，假设有5个城市，每个城市之间有不同的距离，通过全排列可以得到120种（5!）不同的访问顺序，对每种顺序计算总距离，找到最短的那个。
- 资源分配问题：假设有n种资源要分配给m个项目，不同的分配顺序可能会导致不同的收益。将资源看作数组元素，全排列表示不同的分配顺序。通过深度优先搜索全排列，可以找出所有可能的分配顺序，然后计算每种分配顺序下的收益，从而找到最优的分配方案。
密码破解：在密码破解中，如果知道密码是由某些字符组成的全排列中的一种情况。例如，密码是由4位数字组成，且这4位数字是从0 - 9中的4个不同数字组成，那么通过深度优先搜索这10个数字的全排列，然后与目标密码进行匹配，就有可能找到密码。虽然在实际的密码安全中，密码通常会有更复杂的加密方式，但这种全排列搜索在简单的密码破解场景或者密码安全性分析场景中是一种基础的思路。
数据排序算法分析：在分析排序算法的性能时，有时需要生成所有可能的输入数据排列来测试排序算法的稳定性和时间复杂度等特性。全排列可以提供所有可能的输入顺序，通过深度优先搜索生成全排列，然后将这些全排列数据输入到排序算法中进行测试和分析。例如，对于冒泡排序、快速排序等算法，可以使用全排列生成的不同输入数据来观察算法在不同数据顺序下的性能表现。

深搜组合数去悬重

一、深搜组合数的概念

深搜（深度优先搜索）组合数是指在组合数计算或者组合问题求解中运用深度优先搜索算法。组合数从数学上来说，是从nn个元素中抽出rr个元素（不分顺序且r \leq nr≤n）的情况数量。在实际计算组合数或者找出所有组合情况时，深搜可以有效地解决这个问题。

深搜算法本身是一种对图或者树进行遍历的算法，它具有“不撞南墙不回头”的特点。在组合数问题里，我们可以将组合的选择过程看作是在一棵决策树中的搜索过程。例如，从nn个数字1,2,\cdots,n1,2,⋯,n中选取rr个数字的组合，我们可以把每次决定是否选择某个数字当作树的分支。深搜会沿着一条路径不断深入，直到满足某种条件（例如已经选够了rr个数字）或者无法继续（例如剩下的数字数量不足以选够rr个），然后回溯到上一个决策点，尝试其他的分支。这种方式能够遍历所有可能的组合情况。例如，当n = 5n=5，r = 3r=3时，深搜会从第一个数字开始，尝试选择它，然后继续选择下一个数字，直到选够3个数字，这就是一种组合；然后回溯，改变其中某个数字的选择，继续搜索其他的组合情况。这种搜索方式可以通过递归或者使用栈来实现。递归实现深搜组合数时，递归函数会不断调用自身，每一层递归表示一次选择决策，当达到递归边界（例如选够了rr个数字或者所有数字都已经考虑过）时，就得到了一种组合情况。使用栈实现时，栈中保存的是当前的搜索状态，每次将新的状态入栈，当需要回溯时出栈。深搜组合数在处理组合问题时具有很大的优势，尤其是当问题规模不是特别大时，可以方便地找出所有的组合情况。

二、深搜组合数去悬重的方法

（一）排序后比较相邻元素法

当所处理的元素集合存在重复元素时，可以先对元素集合进行排序，这样相同的元素就会相邻。在深搜过程中，当遍历到一个元素时，将其与前一个元素进行比较。如果这个元素和前一个元素相等，并且前一个元素还没有被使用过（取决于具体的使用标记），那么就不使用当前元素进行组合。例如，在一个全排列问题中，如果数组中有重复元素，先将数组排序，在递归的时候判断当前元素是否和其前一个元素值相等，如果相等，再判断前一个元素是否已经在dfsdfs序列中（被使用过），如果前一个元素还没被使用过，则当前元素也无法被使用，其逻辑为(nums [i - 1]==nums [i] \&\&!hm [i - 1])(nums[i−1]==nums[i]&&!hm[i−1]) 。这里numsnums是元素数组，hmhm可以是一个记录元素是否被使用过的数组或者数据结构，ii是当前元素的索引。

（二）使用标记数组或哈希表

可以创建一个标记数组或者哈希表来记录已经使用过的元素或者已经访问过的组合状态。在深搜过程中，每次考虑一个元素或者一种组合状态时，先检查这个元素或者状态在标记数组或哈希表中的标记。如果已经被标记，表示已经处理过，就不再重复处理；如果没有被标记，则进行处理并且标记下来。例如，在组合问题中，对于每一个可能被选择的元素，设置一个布尔类型的标记数组，初始化为falsefalse，表示未被使用。当深搜到某个元素时，先检查其标记，如果为falsefalse，则可以选择该元素并将其标记设为truetrue，继续深搜下一层；当回溯时，再将其标记设回falsefalse，以便其他组合情况可以再次使用该元素。这种方法可以有效避免在深搜过程中重复访问相同的元素或者状态，从而达到去悬重的目的。

（三）剪枝操作

在深搜过程中，根据问题的条件提前判断某些分支不需要继续搜索，从而直接剪掉这些分支。在组合数去悬重方面，如果发现当前搜索路径会产生重复的组合，就停止在这条路径上的搜索。例如，在搜索组合数时，如果按照某种顺序已经确定了前面的几个元素，并且发现继续按照这种顺序搜索下去必然会产生重复的组合（可能是因为之前已经搜索过类似的组合情况），就可以停止在这条路径上的搜索，直接回溯到上一个决策点，尝试其他的分支。剪枝操作需要对问题有深入的理解，能够找到合适的剪枝条件，从而提高深搜的效率并且避免重复计算组合情况。

三、深搜组合数去悬重的实例

（一）全排列中的去悬重实例

假设我们要对数组[1,2,2][1,2,2]进行全排列。

首先对数组进行排序，得到[1,2,2][1,2,2]。
我们使用一个标记数组stst来记录元素是否被使用过，初始化为falsefalse。
开始深搜，假设从第一个元素11开始，将st[0]st[0]标记为truetrue，然后继续深搜下一个位置。
当深搜到第二个位置时，有两种选择22（第一个22）和22（第二个22）。当考虑第一个22时，将st[1]st[1]标记为truetrue，继续深搜。当深搜回溯回来，考虑第二个22时，因为它和第一个22相等，并且第一个22的标记st[1]st[1]在回溯回来时为falsefalse（表示第一个22还没有被完全处理完其他可能的组合），所以按照去悬重的规则，这个第二个22不能被使用，直接跳过，这样就避免了重复的排列。例如，像1,2,21,2,2和1,2,21,2,2（这里两个22的顺序不同但在全排列中是重复的）这种重复的情况就被避免了。
深搜过程中，当到达最后一个位置并且所有元素都按照规则被选择后，就得到了一个不重复的全排列。

（二）组合数计算中的去悬重实例

例如，从[1,2,2,3][1,2,2,3]中选取22个元素的组合。

先排序得到[1,2,2,3][1,2,2,3]。
用一个标记数组或者哈希表来记录元素的使用情况。
开始深搜，从第一个元素11开始，选择11后，再从剩下的元素中选择第二个元素。当考虑第二个22时，由于它和第一个22相等，并且第一个22还没有被完全用于其他组合（如果第一个22在之前的组合中没有被完全处理完其他可能的组合情况），按照去悬重规则，不选择这个第二个22。
这样通过深搜和去悬重的操作，最终可以得到所有不重复的组合，例如1,21,2（这里的22是第一个22），1,31,3等组合，避免了像1,21,2（第一个22）和1,21,2（第二个22）这种重复的组合情况。

四、深搜组合数去悬重的常见问题及解决

（一）标记处理不当导致遗漏组合

问题描述：在使用标记数组或者哈希表进行去悬重时，如果标记的设置和清除时机不正确，可能会导致一些合法的组合被遗漏。例如，在回溯过程中，如果没有正确地将标记恢复为未使用状态，可能会使得后续的搜索无法再次使用某些元素，从而遗漏了包含这些元素的组合。 解决方法：仔细检查标记的设置和清除逻辑。在深搜进入一个新的状态时，正确设置元素的标记为已使用；在回溯时，一定要将标记恢复为未使用状态。例如，在递归实现的深搜中，在递归调用之前设置标记，在递归调用返回（即回溯时）清除标记。并且要对各种可能的情况进行测试，特别是边界情况，确保标记的处理不会影响到所有可能组合的搜索。

（二）比较逻辑错误导致去重不完全

问题描述：当使用比较相邻元素来去悬重时，如果比较逻辑错误，可能无法完全去除重复的组合。例如，只比较了元素的值相等，而没有考虑元素的其他属性或者状态，可能会导致一些看似不同但实际上重复的组合没有被识别出来。 解决方法：除了比较元素的值相等外，还需要根据具体问题考虑元素的其他相关属性。如果是对象类型的元素，可能需要比较对象的多个属性来确定是否真正重复。同时，确保比较的顺序和范围是正确的。在处理复杂数据结构或者对象时，可以重写比较方法或者函数，以确保能够准确地识别重复的元素或者组合情况。

（三）剪枝条件错误导致结果错误

问题描述：在进行剪枝操作时，如果剪枝条件设置错误，可能会剪掉一些不应该剪掉的分支，从而导致得到的组合结果不完整或者错误。例如，剪枝条件过于宽松，可能会错误地剪掉一些还没有完全搜索的分支，导致遗漏组合；剪枝条件过于严格，可能会保留一些本应该被剪掉的重复分支，导致结果中存在重复组合。 解决方法：对剪枝条件进行仔细的分析和验证。通过手动模拟一些简单的例子来验证剪枝条件是否正确。如果可能的话，可以使用一些已知结果的测试数据进行测试。在确定剪枝条件时，要充分考虑问题的各种情况，特别是边界情况和特殊情况。例如，在组合数问题中，要考虑选取元素的数量限制、元素的取值范围、是否有重复元素等因素对剪枝条件的影响。

五、深搜组合数去悬重的优化技巧

（一）优化标记数据结构

使用位运算优化标记数组：如果标记数组中的元素只有两种状态（已使用和未使用，即truetrue和falsefalse），可以考虑使用位运算来表示标记状态。例如，使用一个整数的二进制位来表示多个元素的标记状态，这样可以减少标记数组占用的空间，并且位运算的速度相对较快。假设我们有8个元素需要标记，我们可以使用一个字节（8位）来表示这8个元素的标记状态，每一位对应一个元素的标记。这样在进行标记的设置和检查时，可以通过位运算（如按位与、按位或、按位取反等操作）来高效地完成。
哈希表优化：如果使用哈希表来标记元素或者组合状态，选择合适的哈希函数可以提高哈希表的性能。一个好的哈希函数可以使元素均匀地分布在哈希表中，减少哈希冲突。例如，对于整数元素，可以使用简单的取模哈希函数，但要注意选择合适的模数，避免哈希冲突过于集中。对于复杂对象，可以根据对象的关键属性计算哈希值，并且可以采用一些成熟的哈希算法，如MurmurHash等。此外，根据问题的规模和特点，可以考虑使用不同类型的哈希表，如开散列（链地址法）哈希表或者闭散列（开放定址法）哈希表，以优化哈希表的性能。

（二）调整搜索顺序

按元素大小顺序搜索：在深搜组合数时，可以按照元素的大小顺序进行搜索。例如，在从一组数字中选取组合时，总是先选择较小的数字，这样可以避免一些不必要的搜索。因为如果先选择较大的数字，可能会导致后面的选择范围变小，并且容易产生重复的组合。例如，从1,2,3,4,51,2,3,4,5中选取33个数字的组合，如果先选择55，那么后面的选择范围就只剩下44个数字，而且可能会产生一些与先选择较小数字重复的组合。按照从小到大的顺序选择数字，可以使组合的产生更有规律，也有助于去悬重。
根据元素出现频率搜索：如果知道元素的出现频率，可以先搜索出现频率低的元素。这样在搜索过程中，由于低频元素较少，更容易控制组合的重复性。例如，在一个数组[1,1,2,2,2,3][1,1,2,2,2,3]中，33的出现频率最低，先考虑包含33的组合情况，这样可以减少重复组合的产生。因为如果先从高频元素22开始搜索，会产生大量包含22的组合，后续处理重复情况会更加复杂。

（三）动态调整搜索策略

自适应剪枝：在深搜过程中，根据已经搜索到的结果动态调整剪枝策略。例如，在搜索初期，由于对整体组合情况了解较少，剪枝条件可以相对宽松；随着搜索的进行，当发现某些重复模式或者可以确定某些不可能产生有效组合的情况时，收紧剪枝条件。比如，在搜索组合数时，如果发现已经搜索到的组合中，某些元素的组合总是导致重复，那么可以增加一个剪枝条件，直接剪掉包含这些元素的分支。
记忆化搜索：对于已经计算过的组合情况或者子问题的结果进行记忆。例如，在计算组合数的深搜过程中，如果已经计算过从某几个元素中选取特定数量元素的组合情况，就将这个结果保存下来。当下次再次遇到相同的子问题时，直接使用已经保存的结果，而不需要再次进行深搜。这可以大大减少重复计算，提高搜索效率。记忆化搜索可以使用一个数组或者哈希表来保存已经计算过的结果，在每次进行深搜之前，先检查是否已经有保存的结果，如果有则直接使用，否则进行深搜并保存结果。