DFS应用

深度优先搜索80%用于排序,碰到让找所有方案的题一定用DFS,90%DFS题要么排列要么组合
组合搜索问题:
问题模型:
求出所有满足条件的组合
判断条件:组合中元素是顺序无关的
时间复杂度:与2^n相关
strStr中的subsets问题就是典型组合问题
对于分层遍历用BFS需要同时保存上下几层状态,太费空间,用DFS只需同时保存一条路径的状态(参考视频)
DFS主要就是参数变化的传递

DFS的时间复杂度:
O(答案个数 * 构造每个答案的时间)

时间复杂度在 n!和 2^n的题只能用搜索来做

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

友情链接更多精彩内容