leetcode习题分类汇总- Backtracking篇

N-Queens-返回N格子中N个棋子不能毗邻的所有解法

思路:

这种棋盘类的题目一般是回溯法,依次放置每行的皇后。在放置的时候,要保持当前的状态为合法,即当前放置位置的同一行、同一列、两条对角线上都不存在皇后,其实本质还是DFS,只是加一个判断,然后把结果转化成string,解题的时候注意方法的拆分以保持逻辑清晰,比如判断是否安全一个方法,dfs一个,print一个方法。




N-Queens II-同上,返回所有解法的数量

思路:同上,反而简单了。

Generate Parentheses-给N对(),给出所有的组合方式

思路:DFS+backtraceing+具体判断

1\. Left代表余下的'('的数目

2\. right代表余下的')'的数目

3\. 注意right余下的数目要大于left,否则就是非法的,比如,先放一个')'就是非法的。

4\. 任何一个小于0,也是错的。

5\. 递归的时候,我们只有2种选择,就是选择'('还是选择')'。

6\. 递归的时候,一旦在结果的路径上尝试过'('还是选择')',都需要回溯,即是sb.deleteCharAt(sb.length() - 1);

Permutations-返回数组的全排列

思路:每个数字当可以插入至当前列表的任意位置,明白这点就ok了。

Permutations II-返回有重复数字数组的全排列

思路:只是判断而已。

Combinations-给定1-n以及个数,返回所有组合

思路:用list来做容器,queue来dfs.

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。
当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,
则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。
**SubSets-返回所有子数组,原数组无重复**
思路:dfs,回溯,注意list的浅拷贝和深拷贝。
**SubSets II -返回所有子数组,原数组有重复**
**思路:依然是dfs,回溯,只是要注意消除重复的情况,加到容器里的时候加个判断就可以了,时间n2**
### Combination Sum-给定目标值返回数组中所有=target值的排列组合,元素可以重复利用
思路:**回溯,dfs**,因为不清楚当前元素利用的次数,所以是NP问题。
**Combination Sum II-给定目标值返回数组中所有=target值的排列组合,元素不能重复利用**
**思路:回溯,dfs,和前一题类似,只是返回i+1而已。全排列的问题好像都是一个模型..**
** **

**Combination Sum III -给定元素个数从1-9中选取指定元素,求等于目标值的排列组合。**
**思路:依然是回溯,dfs,只不过传的参数多一点而已**
** **
### Palindrome Partitioning-返回所有回文的切分
思路:返回所有组合的问题一般都是dfs,同上
### Letter Combinations of a Phone Number-给出数字键组合列出所有可能的字母组合。
思路:
先把对应关系存储起来(利用数组下标),然后想办法遍历,DFS或者BFS,可以借助queue
** **

**总结:**
**在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。**
**当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,**
**则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。**
**若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。
常常出现在求所有组合或者排列的题目中,思路往往比较固定。**