深度優(yōu)先搜索/回溯算法(DFS)
Ⅰ 解題套路
? 回溯問(wèn)題實(shí)際上就是一顆決策樹(shù)的遍歷過(guò)程，需要思考三個(gè)問(wèn)題：
- 路徑：也就是已經(jīng)做出的選擇
- 選擇列表：也就是當(dāng)前可以進(jìn)行的選擇
- 結(jié)束條件：也就是到達(dá)決策樹(shù)底層無(wú)法進(jìn)行選擇從而退出的條件
模板代碼：
result = []
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷(xiāo)選擇
//其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」，在遞歸調(diào)用之后「撤銷(xiāo)選擇」
Ⅱ 相關(guān)習(xí)題
1、沒(méi)有重復(fù)數(shù)字的全排列（LeetCode 46）
3
? 我們定義的 backtrack 函數(shù)其實(shí)就像一個(gè)指針，在這棵樹(shù)上游走，同時(shí)要正確維護(hù)每個(gè)節(jié)點(diǎn)的屬性，每當(dāng)走到樹(shù)的底層，其「路徑」就是一個(gè)全排列。
5
List<List<Integer>> res = new LinkedList<>();
/* 主函數(shù)，輸入一組不重復(fù)的數(shù)字，返回它們的全排列 */
List<List<Integer>> permute(int[] nums) {
// 記錄「路徑」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路徑：記錄在 track 中
// 選擇列表：nums 中不存在于 track 的那些元素
// 結(jié)束條件：nums 中的元素全都在 track 中出現(xiàn)
void backtrack(int[] nums, LinkedList<Integer> track) {
// 觸發(fā)結(jié)束條件，表明到底了
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]);
// 進(jìn)入下一層決策樹(shù)
backtrack(nums, track);
// 取消選擇
track.removeLast();
}
}
2、N皇后（LeetCode 51）
? 給你一個(gè) N×N 的棋盤(pán)，讓你放置 N 個(gè)皇后，使得它們不能互相攻擊。PS：皇后可以攻擊同一行、同一列、左上左下右上右下四個(gè)方向的任意單位。這個(gè)問(wèn)題本質(zhì)上跟全排列問(wèn)題差不多，決策樹(shù)的每一層表示棋盤(pán)上的每一行；每個(gè)節(jié)點(diǎn)可以做出的選擇是，在該行的任意一列放置一個(gè)皇后。
image-20201212193833824
class Solution {
public List<List<String>> solveNQueens(int n) {
//初始化棋盤(pá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;
}
//回溯函數(shù)?。。? public void backtrack(char[][] map,int rowDepth,List<List<String>> res) {
//結(jié)束條件
if (rowDepth == map.length) {
//arrToListStr(map) 轉(zhuǎn)化棋盤(pán)的格式
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為當(dāng)前放置皇后的行，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;
}
//棋盤(pán)是一個(gè)二維數(shù)組，要將其轉(zhuǎn)化為每一行是字符串的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）
? 給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。說(shuō)明：解集不能包含重復(fù)的子集。
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)); //所有走過(guò)的路徑都需要記錄，因此沒(méi)有結(jié)束判斷
for (int j=start;j<nums.length;j++) {
path.add(nums[j]);
helper(nums,res,path,j+1);
path.remove(path.size()-1);
}
}
}
可以看見(jiàn)，對(duì) res 的更新是一個(gè)前序遍歷，也就是說(shuō)，res 就是樹(shù)上的所有節(jié)點(diǎn)：
image-20201212200217242
4、組合（LeetCode 77）
? 輸入兩個(gè)數(shù)字 n, k，算法輸出 [1..n] 中 k 個(gè)數(shù)字的所有組合。（要注意剪枝，因?yàn)閇1,2]和[2,1]是相同的，應(yīng)該去重）
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、解數(shù)獨(dú)（LeetCode 37）
? 輸入是一個(gè)9x9的棋盤(pán)，空白格子用點(diǎn)號(hào)字符 ‘.’表示，算法需要在原地修改棋盤(pán)，將空白格子填上數(shù)字，得到一個(gè)可行解。數(shù)獨(dú)的要求：每行，每列以及每一個(gè) 3×3 的小方格都不能有相同的數(shù)字出現(xiàn)。
? 解法：直接對(duì)每個(gè)格子進(jìn)行窮舉，1-9一個(gè)一個(gè)試。與之前的回溯不同的是得到一個(gè)答案就結(jié)束，不要求得出所有答案。
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) { //到達(dá)最后一列
return backtrack (board,row+1,0);
}
if (row == r) { //說(shuō)明9*9的棋盤(pán)都填完了
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] = '.';
}
//都試完了沒(méi)有答案，返回false
return false;
}
// 判斷 board[i][j] 是否可以填入 n
boolean isValid(char[][] board, int r, int c, char n) {
for (int i = 0; i < 9; i++) {
// 判斷行是否存在重復(fù)
if (board[r][i] == n) return false;
// 判斷列是否存在重復(fù)
if (board[i][c] == n) return false;
// 判斷 3 x 3 方框是否存在重復(fù)
if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
return false;
}
return true;
}
}
6、括號(hào)生成（LeetCode 22）
? 數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
? 方法一：n對(duì)括號(hào)就有2*n個(gè)位置，對(duì)這些位置進(jìn)行回溯遍歷，再加上括號(hào)有效性的判斷（用時(shí)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對(duì)括號(hào)分成左括號(hào)（left）n個(gè)，右括號(hào)（right）n個(gè)。由于是從左往右遍歷，一個(gè)合法的括號(hào)生成應(yīng)該是左括號(hào)要大于等于右括號(hào)（用時(shí)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) {
//下面兩個(gè)條件成立說(shuō)明生成括號(hào)不合法
if (left > right) return;
if (left<0 || right<0) return;
//下面成立說(shuō)明生成括號(hào)合法
if (left == 0 && right == 0) {
res.add(sb.toString());
return;
}
//可以不用for循環(huán)，只要列舉完選擇列表就行
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、二叉樹(shù)前序、中序、后序遍歷非遞歸皆為深度優(yōu)先
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;
//注意用這個(gè)方法來(lái)減少引入isVisited數(shù)組
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、目標(biāo)和（用回溯法效率低，可以化為子集背包問(wèn)題 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;
}
//選擇+號(hào)
rest -= nums[depth];
dfs (nums,depth+1,rest);
rest += nums[depth];
//選擇-號(hào)
rest += nums[depth];
dfs (nums,depth+1,rest);
rest -= nums[depth];
}
}
