首页  思维导图  详情



 



回溯

2024-07-15 16:41:10   0  举报





AI智能生成

回溯算法题

回溯

算法

力扣

模板推荐

作者其他创作

大纲/内容

组合

77. 组合

未剪枝

剪枝优化

只改了一句代码，for循环的终止条件

39. 组合总和

未剪枝

剪枝优化

如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。 对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

时间复杂度：，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此 空间复杂度：

17. 电话号码的字母组合

这题无法剪枝优化

216. 组合总和 III

未剪枝

剪枝优化

40. 组合总和II

解析

用startIndex来去重

131. 分割回文串

时间复杂度: O(n * 2^n) 空间复杂度: O(n^2)

思路

93. 复原IP地址

回溯三部曲

1. 递归参数

2. 递归终止条件：走到叶子节点，且分割为4段

3. 单层搜索的逻辑：循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法

代码

子集

78. 子集

 Collect

Get Started

回溯

 Collect

Get Started

回溯

 Collect

Get Started

流程图-数据流转与运维流程图-实现从采集到分析的全过程管理

 Collect

Get Started

回溯





0 条评论

下一页