深度优先搜索/回溯算法(DFS)
Ⅰ 解题套路
回溯问题实际上就是一颗决策树的遍历过程，需要思考三个问题：
- 路径：也就是已经做出的选择
- 选择列表：也就是当前可以进行的选择
- 结束条件：也就是到达决策树底层无法进行选择从而退出的条件
模板代码：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
//其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
Ⅱ 相关习题
1、没有重复数字的全排列（LeetCode 46）
3
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
5
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件，表明到底了
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
2、N皇后（LeetCode 51）
给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
image-20201212193833824
class Solution {
public List<List<String>> solveNQueens(int n) {
//初始化棋盘
char[][] map = new char[n][n];
int row = map.length;
int col = map[0].length;
for (int i=0;i<row;i++) {
for (int j=0;j<col;j++) {
map[i][j] = '.';
}
}
List<List<String>> res = new ArrayList<>();
backtrack(map,0,res);
return res;
}
//回溯函数！！！
public void backtrack(char[][] map,int rowDepth,List<List<String>> res) {
//结束条件
if (rowDepth == map.length) {
//arrToListStr(map) 转化棋盘的格式
res.add(arrToListStr(map));
return;
}
for (int i=0;i<map.length;i++) {
if (judge(map,rowDepth,i)) {//如果放置的皇后不冲突
map[rowDepth][i] = 'Q';
backtrack(map,rowDepth+1,res);
map[rowDepth][i] = '.';
}
}
}
//判断皇后是否冲突 。row为当前放置皇后的行，col为列
public boolean judge(char[][] map,int row,int col){
//该皇后的同一列是否有皇后
for (int i =0;i<row;i++) {
if (map[i][col] == 'Q') {
return false;
}
}
//判断左上角(整条斜线)是否有皇后
for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
if (map[i][j] == 'Q') {
return false;
}
}
//判断右上角(整条斜线)是否有皇后
for (int i=row-1,j=col+1;i>=0&&j<map.length;i--,j++) {
if (map[i][j] == 'Q') {
return false;
}
}
return true;
}
//棋盘是一个二维数组，要将其转化为每一行是字符串的List集合
public List<String> arrToListStr(char[][] arr) {
List<String> path = new ArrayList<>();
for (int i=0;i<arr.length;i++) {
path.add(new String(arr[i]));
}
return path;
}
}
3、子集（LeetCode 78）
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
if (len == 0) return res;
helper(nums,res,path,0);
return res;
}
public void helper(int[] nums,List<List<Integer>> res,List<Integer> path,int start) {
res.add(new ArrayList<>(path)); //所有走过的路径都需要记录，因此没有结束判断
for (int j=start;j<nums.length;j++) {
path.add(nums[j]);
helper(nums,res,path,j+1);
path.remove(path.size()-1);
}
}
}
可以看见，对 res 的更新是一个前序遍历，也就是说，res 就是树上的所有节点：
image-20201212200217242
4、组合（LeetCode 77）
输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。（要注意剪枝，因为[1,2]和[2,1]是相同的，应该去重）
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if (n == 0 || k == 0 || k > n) return new ArrayList<>(0);
List<Integer> path = new ArrayList<>();
banktrack(n,k,path,1);
return res;
}
void banktrack (int n,int k,List<Integer> path,int start) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int i=start;i<=n;i++) {
path.add(i);
//注意是i+1不是start+1
banktrack(n,k,path,i+1);
path.remove(path.size()-1);
}
}
}
5、解数独（LeetCode 37）
输入是一个9x9的棋盘，空白格子用点号字符 ‘.’表示，算法需要在原地修改棋盘，将空白格子填上数字，得到一个可行解。数独的要求：每行，每列以及每一个 3×3 的小方格都不能有相同的数字出现。
解法：直接对每个格子进行穷举，1-9一个一个试。与之前的回溯不同的是得到一个答案就结束，不要求得出所有答案。
class Solution {
public void solveSudoku(char[][] board) {
backtrack(board,0,0);
}
boolean backtrack ( char[][] board ,int row,int col ) {
int r = 9; int c = 9;
if (col == c) { //到达最后一列
return backtrack (board,row+1,0);
}
if (row == r) { //说明9*9的棋盘都填完了
return true;
}
if (board[row][col] != '.') {
return backtrack(board,row,col+1);
}
for (char ch = '1';ch <= '9';ch++) {
if (!isValid(board,row,col,ch)) continue;
board[row][col] = ch;
if (backtrack(board,row,col+1)) return true;
board[row][col] = '.';
}
//都试完了没有答案，返回false
return false;
}
// 判断 board[i][j] 是否可以填入 n
boolean isValid(char[][] board, int r, int c, char n) {
for (int i = 0; i < 9; i++) {
// 判断行是否存在重复
if (board[r][i] == n) return false;
// 判断列是否存在重复
if (board[i][c] == n) return false;
// 判断 3 x 3 方框是否存在重复
if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
return false;
}
return true;
}
}
6、括号生成（LeetCode 22）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
方法一：n对括号就有2*n个位置，对这些位置进行回溯遍历，再加上括号有效性的判断（用时13ms，效率低）：
class Solution {
public List<String> generateParenthesis(int n) {
if (n <= 0) {
res.add("");
return res;
}
StringBuilder sb = new StringBuilder();
char[] opt = {'(',')'};
backtrack(n,sb,opt);
return res;
}
List<String> res = new ArrayList<>();
void backtrack (int n,StringBuilder sb,char[] opt) {
if (sb.length() == n*2) {
String path = sb.toString();
if (isValid(path,n)) {
res.add(path);
}
return;
}
for (int i=0;i<=1;i++) {
sb.append(opt[i]);
backtrack(n,sb,opt);
sb.deleteCharAt(sb.length()-1);
}
}
boolean isValid (String path,int n) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch:path.toCharArray()) {
if (ch == '(') {
stack.addLast(ch);
}else if (ch == ')') {
if (stack.size() == 0) {
return false;
}else {
stack.removeLast();
}
}
}
return stack.size()==0?true:false;
}
}
方法二：将n对括号分成左括号（left）n个，右括号（right）n个。由于是从左往右遍历，一个合法的括号生成应该是左括号要大于等于右括号（用时1mm，效率高）。
class Solution {
public List<String> generateParenthesis(int n) {
if (n <= 0) {
res.add("");
return res;
}
backtrack(n,n,new StringBuilder());
return res;
}
List<String> res = new ArrayList<>();
void backtrack (int left,int right,StringBuilder sb) {
//下面两个条件成立说明生成括号不合法
if (left > right) return;
if (left<0 || right<0) return;
//下面成立说明生成括号合法
if (left == 0 && right == 0) {
res.add(sb.toString());
return;
}
//可以不用for循环，只要列举完选择列表就行
sb.append('(');
backtrack(left-1,right,sb);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
backtrack(left,right-1,sb);
sb.deleteCharAt(sb.length()-1);
}
}
7、二叉树前序、中序、后序遍历非递归皆为深度优先
二叉树的跳转连接
8、矩阵中的路径——寻找单词（剑指offer 12）
image-20201216225638764
class Solution {
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return false;
char[] wordArr = word.toCharArray();
for (int i=0;i<board.length;i++) {
for (int j=0;j<board[0].length;j++) {
if (dfs(board,wordArr,i,j,0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
//递归出口
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if(k == word.length - 1) return true;
//注意用这个方法来减少引入isVisited数组
board[i][j] = '#';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
}
9、目标和（用回溯法效率低，可以化为子集背包问题 LeetCode 494）
image-20201220203847478
class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0) return 0;
dfs(nums,0,S);
return res;
}
int res = 0;
//rest是剩余的值，rest=0才满足要求
void dfs (int[] nums,int depth,int rest) {
if (depth == nums.length) {
if (rest == 0) {
res++;
}
return;
}
//选择+号
rest -= nums[depth];
dfs (nums,depth+1,rest);
rest += nums[depth];
//选择-号
rest += nums[depth];
dfs (nums,depth+1,rest);
rest -= nums[depth];
}
}
