登录免费注册



首页  思维导图  详情



回溯

2023-04-25 17:10:27   0  举报





AI智能生成

算法

知识管理

模版推荐

作者其他创作

大纲/内容

思想：回溯本质是穷举，使用递归穷举各种可能性；简单说就是从一条路走到头，然后回来选择另一条路再继续走，直到走完左右的情况。<br>

注意：回溯需要考虑剪枝，比如n取k，剩余全选都不足k个，则需要剪枝；全选都加不到sum，则需要剪枝

注意：backtracking递归纵向遍历，for循环横向遍历

组合

单个集合求组合

需要startIndex

作用：组合不要求顺序，需要保证遍历过的不能再遍历

1.不能多次使用同一个元素-每次递归传入的startIndex值为i+1

77.组合<br>

2.可以多次使用一个元素--每次递归传入的startIndex值为i

216.组合总和III<br>

多个集合求组合

<b>不需要startIndex（注意这是唯一不用startIndex的）</b>

17.电话号码的字母组合<br>

切割问题

组合问题：startIndex表示至少从哪里开始选，for循环表示选择哪一个

切割问题，startIndex表示至少从哪里开始切，for循环遍历选择切到哪里（切到i位置之后）<br>

子集问题

组合问题：仅仅收集叶子结点的结果<br>

子集问题：需要收集所有结点的结果

当然也有的要求至少两个结点的，类子集问题

491.递增子序列<br>

n个数中有重复元素，则需要去重（树层去重）

1.递归遍历完以后，用while循环去重

2.使用used数组

排列

要求顺序，横向上用过的还可以用，所以不能使用startIndex

没有startIndex，需要保证纵向上用过的不能再使用

使用used数组来保证同一树枝上不重复使用

n个数中有重复元素，需要去重

使用used数组保证同一树层上用过的不重复使用

棋盘

todo

 Collect

Get Started

递归-迷宫回溯

 Collect

Get Started

回溯

 Collect

Get Started

回溯-改进

 Collect

Get Started

批量问题升级流程













评论

0 条评论

下一页



图形选择

思维导图

主题

补充说明

AI生成





修改AI描述

去编辑

重新生成

提示 

关闭后当前内容将不会保存，是否继续？

取消

确定

Document