3. BFSDFS回溯.md

[TOC]

一、DFS

695 最大岛屿面积

给定二维01矩阵，求“连续1”的最大个数

547 朋友圈

OFFER13 机器人的运动范围

给定行列数m和n，机器人从（0,0）出发，不能待在行列数位和大于k的格子中，求机器人能够到达的格子数

剑指OFFER 12 单词搜索/矩阵中的路径

给定二维char矩阵，并给定一个字符串word，搜索该字符串在board中是否存在

417太平洋大西洋水流问题

二、BFS

934 最短的桥

126 单词接龙（Hard）

三. 回溯法

sort的必要性

1. 树枝剪枝需要，在target问题中，出现大于target的值直接返回，这一点依赖于一个事实：数组后面的值只会比现在访问到的更大
2. 同层剪枝需要，保证同样大小的数在一块，当前一个元素与当前相同但是却没被使用过时，意味着正在发生同层的重复，这时要及时剪枝。这一点的实现也依赖于数组排序。

数组中有重复元素---> 使用used同树层去重

数组元素可被无限制选取-----> 使用used没有用，因为即使被用过的元素仍然可被使用 startIndex从i+1变为i

但是对于组合，可以用used数组去重，==也可以用startIndex==

剪枝：排序+剪枝是常用手法

排列问题与组合问题的区别：

1. 排列问题startIndex--->0，转向使用isused保证元素非重复选用

2. 与组合问题不同，排列问题的元素一般不会被无限制选取，因为这样的话排列将会有无穷多个

   排列求和其实挺诡异的，因此一般都是组合求和，排列求全排列？既然时求全排列，那么数组元素无限制选取这种条件就不可能出现的了，要不然排列就会有无穷多个的

   如果真的有排列求和？

   数组元素无限制选取 used不用+排列特性

   数组元素有重复： used同树层剪枝

3.1 组合问题

77 组合

给定n,k，求从1~n中选取k的数字的所有组合

216 组合总和③

给定n,k，求1~9的k个数组成和为n的组合个数

39 组合总和

给定无重复元素的数组candidates和target，可无限制选取元素，求和为target的组合

40 组合总和②

给定可能含有重复元素的数组candidates和target，求和为target的组合

有重复元素：同树层去重

3.2 排列问题

46 全排列

给定不含重复数字的nums，无target，求全排列

47全排列②

给定含重复数字的nums，求全排列

3.3 切割问题

131 分割回文串

分割问题的实质就是选择在哪切，而且前面切的结果会对后面切的结果产生影响

切并不限制一次切掉多少个，因此切完所用的刀数不一定。但切的最终目的都只有一个，那就是把整个字符串全部切完。因此这涉及到一个问题：即切的进度 对应于组合或者排列的组合和/排列和

那到底是排列问题还是组合问题呢？

93 复原IP地址

3.4 子集问题：

78 子集

90子集②

3.5 棋盘问题：

51 N皇后

37 解数独

3.6 其他问题

79 单词搜索

491递增子序列

332重新安排行程

Tips

对于组合：startIndex必备

startIndex+1---> i+1

回溯backtracing：函数形参，终止条件，递归逻辑

回溯的写法：肉夹馍

回溯是因为路径信息需要擦除

常用两个数组：path result

//数组排序

sort(candidates.begin(),candidates.end());

runtime error <stl_vector.h>多半是因为数组下标访问越界

candidates[i-1]