回溯
2023-04-25 17:10:27 0 举报AI智能生成
算法
作者其他创作
大纲/内容
思想：回溯本质是穷举，使用递归穷举各种可能性；简单说就是从一条路走到头，然后回来选择另一条路再继续走，直到走完左右的情况。
注意：回溯需要考虑剪枝，比如n取k，剩余全选都不足k个，则需要剪枝；全选都加不到sum，则需要剪枝
注意：backtracking递归纵向遍历，for循环横向遍历
作用：组合不要求顺序，需要保证遍历过的不能再遍历
77.组合
1.不能多次使用同一个元素-每次递归传入的startIndex值为i+1
216.组合总和III
2.可以多次使用一个元素--每次递归传入的startIndex值为i
需要startIndex
单个集合求组合
17.电话号码的字母组合
不需要startIndex（注意这是唯一不用startIndex的）
多个集合求组合
组合问题：startIndex表示至少从哪里开始选，for循环表示选择哪一个
切割问题，startIndex表示至少从哪里开始切，for循环遍历选择切到哪里（切到i位置之后）
切割问题
131.分割回文串；93.复原IP地址
组合问题：仅仅收集叶子结点的结果
子集问题：需要收集所有结点的结果
491.递增子序列
当然也有的要求至少两个结点的，类子集问题
子集问题
78.子集；90子集II
1.递归遍历完以后，用while循环去重
2.使用used数组
n个数中有重复元素，则需要去重（树层去重）
组合
要求顺序，横向上用过的还可以用，所以不能使用startIndex
使用used数组来保证同一树枝上不重复使用
没有startIndex，需要保证纵向上用过的不能再使用
使用used数组保证同一树层上用过的不重复使用
n个数中有重复元素，需要去重
排列
todo
棋盘
回溯
0 条评论
回复 删除
下一页
