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