DFS & 回溯

回溯算法详解（修订版）

东哥又来扒套路了，框架思维，以不变应万变。

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&scene=19#wechat_redirect

回溯算法牛逼！

k 个桶（集合），记录每个桶装的数字之和 int[] bucket = new int[k]; // 穷举 nums 中的每个数字 { // base case if (index == nums.length) { return; } // 穷举每个桶 for (int i = 0; i < bucket.length; i++) { // 选择装进第 i 个桶 bucket[i] += nums[index]; // 递归穷举下一个数字的选择 backtrack(nums, index + 1); // 撤销选择 bucket[i] -= nums[index]; } }

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247490981&idx=1&sn=db17864d2f6f189d63e051e434c05460&scene=19#wechat_redirect

分割等和子集

子集or组合

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）形成一个子集。一个子集又可以称为一个组合。如果两个子集（组合）的元素完全相同只是顺序不同，那么它们可以看作同一个子集（组合）。 子集和组合定义是相同的

排列

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）并按照某种顺序形成一个排列。m等于n的排列又称为全排列。如果两个排列的元素完全相同只是顺序不同，那么它们就是两个不同的排列。也就是说，排列与元素的顺序相关，这一点与组合不同。

分割字符串

棋盘问题

二维矩阵搜索问题

• 是否已经到达路径终点

• 当前位置是否越界，判断i j

• 当前位置是否已经走过一遍， 通常借助used数组来判断

• 当前位置是否还可行

搜索问题

路径问题

565. 数组嵌套

记忆化搜索问题

LCP 07. 传递信息

851. 喧闹和富有

688. 骑士在棋盘上的概率

6110. 网格图中递增路径的数目

总结

• 内存开销较小，每次只维护一个节点

• 能处理子节点较多或者树层过深的问题（相比BFS）

• 可以用来解决联通性问题（是否有解）

• 只能寻找有解但无法找到最优解（寻找最优解需要遍历所有路径，然后比较得到最优解）

Tips

• 在每一层，初始化一个空set,然后遍历元素时，判断是否已经在集合中了，如果不在，则添加进去。然后向下一层搜索。如果已经在集合中了，则continue。 对于此种方式，也是需要排序的！！因为不排序的话，对于 4，1，4会出现[4,1] [1, 4]这两种相同的集合or组合

• 因为是排好序的，所以直接采用 if i > start and nums[i] == nums[i-1] :continue 这种方式达到去重目的。

记录