穷举vs暴搜vs深搜vs回溯vs剪枝

作者：小蓝xlanll | 2024-05-03 01:53:16

踩

穷举vs暴搜vs深搜vs回溯vs剪枝

1、全排列

46. 全排列 - 力扣（LeetCode）

why？为什么这道题可以全排列？

首先这道题，本身就是一种穷举类的题。

像这类穷举的题用for循环是很难写的。

1、首先画出决策树：越详细越好

由此我们发现，在每一个空格处都是干的同样的事，都是枚举数组中的每一个数，因此我们可以使用递归。

2、设计代码：

全局变量：

全局变量的设计就看递归过程中涉及什么东西，并且看返回什么东西。

首先全局的结果数组：int[][] ret；

然后int[] path；path的作用就是在深度优先遍历决策树的途中记录一下我们的路径。也可以看作恢复现场。当path的长度等于nums的长度时，就说明发现了一种情况。当我们往回走的时候，就将path的最后一个数pop掉，就是恢复现场了。

最后如何剪枝呢？我们使用bool[] check；来判断是否重复使用，check里面记录的是nums中的下标。如：nums[1,2,3]，当使用2时，将check[1] = true；

dfs函数：

重复子问题---函数头

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/527163