回溯
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 条评论
回复 删除
下一页