深度优先搜索（DFS，DepthFirstSearch）简称深搜或者爆搜，DFS的搜索顺序是按照深度优先搜索，简单来说就是“一条路走到黑”，搜索是把所有方案都试一遍，再判断是不是一个可行解。搜索与“递归”和“栈”有很大的联系，递归是实现搜索的一种方式，而栈则是计算机实现递归的方式。每个搜索过程都对应着一棵递归搜索树，递归搜索树可以让我们更加容易的理解DFS。整个搜索过程就是基于该搜索树完成的，为了不重复遍历每个结点，会对每个结点进行标记，也可以对树中不可能是答案的分支进行删除，从而更高效的找到答案，这种方法被称为剪枝。如果搜索树在某个子树中搜索到了叶结点，想继续搜索只能返回上个或多个状态，返回的过程称为回溯，回溯要记得恢复状态，才能保证接下来的搜索过程可以正常进行。
题意：输出$n$的全排列
思路：以$n$为$3$举例，枚举每个位置上该填什么数，但是每一位上的数不能和其他位置上的数一样，填满了$3$位就输出，然后回溯继续搜索。
上图则是一棵递归搜索树，就是搜索的过程形象化的显示出来。从第一个数字开始填，在填第二个数字，填过的数字记得要标记一下“使用过了”，不然会导致三个数字有两个数字是重复的。上文提到的回溯，就是填完了三个数字，先输出答案，无法在继续搜索下去就要回溯，回溯记得要恢复状态，不然接下来无法填数。
算法思路：
intpath[10],st[10],n;voiddfs(intu){if(u==n)//u==n则说明填满了三个数{for(inti=0;i DFS的思想和代码很容易理解，这里不再赘述，但初学者学不懂DFS的原因主要是不理解递归而理解不了DFS。这里来详细的讲解一下递归的执行过程。 进入入口则是主函数调用，先执行一段代码然后递归调用（对应上面的代码就是dfs(u+1)），如果某一次递归的过程的中触发了判断条件，则返回（回溯），回溯到上次执行我这次的递归的代码的下面再继续执行下面的代码，如图中的第一根红线，对应上面的代码是先输出了$123$，然后是第一次触发判断条件，这时$u$为$3$，就返回到$u$为$2$的这次递归上，然后不执行dfs(u+1)，直接执行下面的代码。然后没代码可以执行了，就只能执行第$27$行的代码继续返回（回溯），然后再继续做接下来的操作。 剪枝的常见方法： 题目大意：给定若干个长木棍和若干的短木棍，让我们从长木棍中裁剪出若干个短木棍，问我们最多可以裁出多少根短木棍。每个长木棍和短木棍只能使用一次。 思路：数据范围只有$m\leq50$所以直接深搜就行了，但需要加一点剪枝优化。 剪枝$1$ 排序$+$二分 先将长木棍和短木棍从小到大排序。 显然，我们裁的时候一定是从小到大裁剪的前$k$个，不妨设我们裁剪的不是最小的$k$个，那么我们裁剪最小的$k$个，方案数不会变少。 所以只需要裁剪从小到大的前$k$的短木棍就可以了，所以需要存一个短木棍的前缀和S[i]。 我们还可以发现，如果裁剪的是前$k$个短木棍的话，那么在$k$之前的一定可以裁剪，在$k$之后的一定不能裁剪，所以具有二段性，所以就可以二分了。 剪枝$2$（优化搜索顺序） 我们在判断前$k$个短木棍能不能裁剪出来的时候，直接搜索就可以了，可以从后往前枚举（即从大到小）短木棍。 从大到小枚举可以使搜索树的分支更少，从而更快的触发剪枝条件。 剪枝$3$（可行性剪枝） 我们开一个变量total来记录所有长木棍的总长度，如果total 剪枝$4$ 如果某个长木棍的长度都要$<$最短的木棍的长度的话，那么也一定无解。