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