回溯
2024-07-15 16:41:10 0 举报AI智能生成
回溯算法题
作者其他创作
大纲/内容
未剪枝
只改了一句代码，for循环的终止条件
剪枝优化
77. 组合
如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
时间复杂度：，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此空间复杂度：
39. 组合总和
这题无法剪枝优化
17. 电话号码的字母组合
216. 组合总和 III
解析
用startIndex来去重
40. 组合总和II
时间复杂度: O(n * 2^n)空间复杂度: O(n^2)
思路
131. 分割回文串
1. 递归参数
2. 递归终止条件：走到叶子节点，且分割为4段
回溯三部曲
代码
93. 复原IP地址
组合
78. 子集
子集
回溯
0 条评论
回复 删除
下一页
