题型一:排列、组合、子集相关问题
提示:这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是:先画图,再编码。去思考可以剪枝的条件, 为什么有的时候用 used 数组,有的时候设置搜索起点 begin 变量,理解状态变量设计的想法。
- 全排列(中等)
- 全排列 II(中等):思考为什么造成了重复,如何在搜索之前就判断这一支会产生重复;
- 组合总和(中等)
- 组合总和 II(中等)
- 组合(中等)
- 子集(中等)
- 子集 II(中等):剪枝技巧同 47 题、39 题、40 题;
- 第 k 个排列(中等):利用了剪枝的思想,减去了大量枝叶,直接来到需要的叶子结点;
下面这几个问题,思想不难,但是初学的时候代码很不容易写对,并且也很难调试。我们的建议是多写几遍,忘记了就再写一次,参考规范的编写实现(设置 visited 数组,设置方向数组,抽取私有方法),把代码写对。
- 图像渲染(Flood Fill,中等)
- 岛屿数量(中等)
- 被围绕的区域(中等)
- 单词搜索(中等)
说明:以上问题都不建议修改输入数据,设置 visited 数组是标准的做法。可能会遇到参数很多,是不是都可以写成成员变量的问题,面试中拿不准的记得问一下面试官
题型三:字符串中的回溯问题
提示:字符串的问题的特殊之处在于,字符串的拼接生成新对象,因此在这一类问题上没有显示「回溯」的过程,但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型,是希望朋友们能够注意到这个非常细节的地方。
- 电话号码的字母组合(中等),题解;
- 字母大小写全排列(中等);
- N 皇后(困难):其实就是全排列问题,注意设计清楚状态变量,在遍历的时候需要记住一些信息,空间换时间;
- 解数独(困难):思路同「N 皇后问题」;
- 祖玛游戏(困难)
- 扫雷游戏(困难)
需要精读的两篇文章