普通回溯算法总结

矫情吗；* 2024-04-03 08:53 76阅读 0赞

回溯分为3类：  
1.要不要向上回溯  
2.是否跳过重复元素  
3.棋盘格

## 1.要不要向上回溯 ##

### 1.1需要向上回溯 ###

#### lc17 ####

![在这里插入图片描述][6bedccb5c96a44a7bc883cc0ac5beb03.png]  
ps:普通回溯通法  
1.定义返回类型（第3行）  
2.定义Deque path = new ArrayDeque<>();（只有两层的返回类型才定义这个，比如List<List> 或者List（相当于List<List>）都是两层list，一层的不用定义ArrayDeque，这是个双端队列，前后都可以添加删除元素）  
3.把所有定义的变量都加进dfs的参数，再加个0  
![在这里插入图片描述][1a9ba4d24ed548bb907be39d276fef68.png]  
![在这里插入图片描述][02669c221d5944ceb59356a553bfe07b.png]  
这是需要向上回溯的，第24行从0开始到s.length遍历，第26行只需在刚才0的元素+1（14行0的位置）

#### lc 46 ####

![在这里插入图片描述][107ae9bebb0b4f79b6a2e964c29c3bf7.png]  
这题也需要向上回溯，且不需要重复走（一般需要向上回溯的都不需要重复走）  
16行遍历0到len 20行只需在0的位置+1（7行0的位置）

### 1.2不需要向上回溯 ###

#### lc 78 不需要向上回溯且无重复元素 ####

![在这里插入图片描述][cffec2bb61844c688ed7be685d302cd4.png]  
每次这个节点走完之后不需要再走这个节点之前的元素了，每次都是从这个节点往后走，对于不向上回溯的10行的遍历是从s开始（向上遍历的是从0开始），12行dfs是i+1（向上回溯是s+1）

#### lc39 不需要向上回溯且有重复元素 ####

![在这里插入图片描述][b2003745b60f4abcb92767d54c78a439.png]  
每次这个节点走完之后不需要再走这个节点之前的元素了，每次都是从这个节点往后走，但是这个节点可能走两遍（2，2，3）（有重复元素）  
对于不向上回溯的18行的遍历是从si开始（向上遍历的是从0开始），20行的0位置是i(非重复节点是i+ 1)

[6bedccb5c96a44a7bc883cc0ac5beb03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/6be95698b8154f0cb620b0914d333f17.png
[1a9ba4d24ed548bb907be39d276fef68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f2b20ad7567a4ee39d823cdfdd89a1c5.png
[02669c221d5944ceb59356a553bfe07b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/6f402cf2eadb48f7910514076011d999.png
[107ae9bebb0b4f79b6a2e964c29c3bf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/39b2fa13c2aa45938b03ee9570dc65c3.png
[cffec2bb61844c688ed7be685d302cd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/90455458aea7473ea63758fe3e37c33c.png
[b2003745b60f4abcb92767d54c78a439.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f1434e69123a4feabd231c015488f1f0.png