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