概念
回溯算法是一种类似枚举的搜索算法，按照一定的条件搜索解，如果发现不满足就退回一步，重新选择其他分支进行搜索，许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
通常做法是：在包含问题的所有解的解空间树（回溯树）中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
特点及与其他算法的对比
-
回溯算法一般情况下用在求所有的解的情况（或很多解，但也有特殊情况，比如数独问题，要想求出来所有的解时间复杂度太高，所以找到一个解之后就要停止递归）
-
动态规划一般用在求一个最值的情况
-
dfs一般用在不知道几层循环（dfs并不是一类独立的算法，只是一种搜索的方法，回溯法可以被认为是一个有过剪枝的DFS过程）
用回溯算法解题的步骤
首先画出回溯算法的决策树，把选择标在边上，节点旁边画上当前状态的待选列表和路径，例如
比如要对[1, 2, 3]全排列，画出回溯树
o
/ | \
1/ |2 \3
/ | \
o o o
/ \
2/ \3 ...
/ \
o o
| |
3| |2
| |
o o
画好回溯树之后注意观察树的高度、宽度和如何剪枝等
然后套算法模板
result = []
def backtrack(路径, 待选列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 待选列表:
做选择
backtrack(路径, 待选列表)
撤销选择
几个经典题目
求子集
实际上这题也可以用分治法解决，但时间复杂度较高
def func1(lst):
res = []
def backtrack(routes, start): # routes记录路径（即子集），start记录开始位置（间接记录剩下的选择）
res.append(routes.copy())
for i in range(start, len(lst)):
routes.append(lst[i])
backtrack(routes, i+1)
routes.pop()
backtrack([], 0)
return res
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> route = new ArrayList<>();
backtrack(res, route, nums, 0);
return res;
}
public void backtrack(List<List<Integer>> res, List<Integer> route, int[] nums, int start){
List<Integer> routeCopy = new ArrayList<>(route);
res.add(routeCopy);
// 常用方法，
for(int i=start; i<nums.length; i++){ // 所有可能的选择
// 做选择
route.add(nums[i]);
backtrack(res, route, nums, i+1); // 这里传i+1
// 撤销选择
route.remove(route.size()-1);
}
}
}
求排列 计算A(n, m)
# A(n, m) = n!/(n-m)! = n(n-1)(n-2)...(n-m+1)
def func3(n, m):
res = []
def backtrack(routes, choices):
if len(routes) == m:
res.append(routes.copy())
return
for choice in choices:
if choice in routes: # 排除不合法的选择
continue
routes.append(choice)
backtrack(routes, choices)
routes.pop()
backtrack([], [i for i in range(1, n+1)])
return res
class Solution {
public List<List<Integer>> permute(int[] nums) {
boolean[] selected = new boolean[nums.length];
for(int i=0; i<nums.length; i++){
selected[i] = false;
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> routes = new ArrayList<>();
backtrack(res, routes, nums, selected);
return res;
}
public static void backtrack(List<List<Integer>> res, List<Integer> routes, int[] choices, boolean[] selected){
if(routes.size() == choices.length){
// System.out.println(routes);
List<Integer> temp = new ArrayList<>();
// Collections.copy(temp, routes);
temp.addAll(routes);
res.add(temp);
}
// 不能重复选择元素
for(int i=0; i<choices.length; i++){ // 所有可能的选择
if (! selected[i]){
int current_choice = choices[i];
// 做选择
selected[i] = true;
routes.add(current_choice);
// 递归调用
backtrack(res, routes, choices, selected);
// 撤销选择
selected[i] = false;
routes.remove(routes.size()-1);
}
}
}
}
求组合 计算C(n, m)
# C(n, m) = A(n, m)/m!
def func2(n, m):
res = []
def backtrack(routes, start): # start从1开始
if len(routes) == m:
res.append(routes.copy())
return
for choice in range(start, n+1):
routes.append(choice)
backtrack(routes, choice+1)
routes.pop()
backtrack([], 1)
return res
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums = new int[n];
for(int i=0; i<n; i++){
nums[i] = i+1;
}
// System.out.println(Arrays.toString(nums));
boolean[] selected = new boolean[n];
for(int i=0; i<n; i++){
selected[i] = false;
}
backtrack(res, path, nums, selected, 0, k);
return res;
}
public void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] selected, int start, int k){
if(path.size() == k){
List<Integer> pathCopy = new ArrayList<>(path);
res.add(pathCopy);
// System.out.println(res);
}
for(int i=start; i<nums.length; i++){
path.add(nums[i]);
backtrack(res, path, nums, selected, i+1, k);
path.remove(path.size()-1);
}
}
}
电话号码的字母组合
leetcode 17
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例: 输入：”23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
def func(digits):
if digits == "":
return []
lst = ["", "", "abc", 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
def backtrack(route, choices): # 参数为路径和待选列表
if not choices: # 如果满足结束条件
res.append(route) # 记录或输出
return
for choice in choices: # 遍历所有剩余的选择
route += choice # 做出当前选择
updated_choices = [] # 更新choices，即看看下一轮还剩下什么选择
if (len(route) < len(digits)):
for c in lst[int(digits[len(route)])]:
updated_choices.append(c)
backtrack(route, updated_choices)
route = route[:-1] # 撤销选择
res = []
backtrack("", lst[int(digits[0])])
return res
class Solution {
public List<String> letterCombinations(String digits) {
if(digits.equals("")){
return new ArrayList<>();
}
String[] map = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
char[] digitsArray = digits.toCharArray();
List<String> res = new ArrayList<>();
backtrack(res, "", digitsArray, 0, map);
return res;
}
public void backtrack(List<String> res, String path, char[] digitsArray, int position, String[] map){
if(path.length() == digitsArray.length){
// System.out.println(path);
res.add(path);
}
String choices = "";
if(position < digitsArray.length){
choices = map[digitsArray[position] - '0'];
}
for(int i=0; i<choices.length(); i++){
path += choices.charAt(i);
backtrack(res, path, digitsArray, position+1, map);
path = path.substring(0, path.length()-1);
}
}
}
组合总和
leetcode 39
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
def func2(candidates, target):
# 每次考虑过的元素就不作为选择了，这样可以避免重复。（并不会导致有可行解找不到）
# 每次更新choices，从当前选择的元素往前（包括）
res = []
def backtrack(route, choices):
if sum(route) == target:
res.append(route.copy())
return
if sum(route) > target:
return
for c in choices:
route.append(c)
temp = []
flag = False
for i in choices: # 由于choices里面没有重复的元素，所以这样可以保证每次从c右边开始选（包括c）
if i == c:
flag = True
if flag:
temp.append(i)
backtrack(route.copy(), temp)
route.pop()
backtrack([], candidates)
return res
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(res, path, 0, candidates, target);
return res;
}
// 类似求所有的子集
public void backtrack(List<List<Integer>> res, List<Integer> path, int start, int[] candidates, int target){
// System.out.print("#");
// System.out.println(path);
int sum = 0;
for(int x : path){
sum += x;
}
if(sum>target){
return;
}
// System.out.println(sum);
if(sum == target){
// System.out.println(path);
List<Integer> pathCopy = new ArrayList<>(path);
res.add(pathCopy);
}
for(int i=start; i<candidates.length; i++){
path.add(candidates[i]);
backtrack(res, path, i, candidates, target);
path.remove(path.size()-1);
}
}
}
N皇后
leetcode 51
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例: 输入: 4 输出: [ [“.Q..”, // 解法 1 “…Q”, “Q…”, “..Q.”], [”..Q.”, // 解法 2 “Q…”, “…Q”, “.Q..”] ]
def genBoard(n):
t = []
for i in range(n):
t.append("." * n)
return t
def isValid(n, r, c, board):
if "Q" in board[r]:
return False
for row in board:
if row[c] == "Q":
return False
p, q = r, c
while 0<=p<n and 0<=q<n: # ↘
if board[p][q] == "Q":
return False
p+=1
q+=1
p, q = r, c
while 0<=p<n and 0<=q<n: # ↗
if board[p][q] == "Q":
return False
p+=1
q-=1
p, q = r, c
while 0<=p<n and 0<=q<n: # ↙
if board[p][q] == "Q":
return False
p-=1
q+=1
p, q = r, c
while 0<=p<n and 0<=q<n: # ↖
if board[p][q] == "Q":
return False
p-=1
q-=1
return True
def func(n):
def backtrack(board, r):
# r表示第r行已经被放置皇后
if r == n:
# 如果已经放到了最后一行，那么保存结果，结束递归
res.append(board.copy())
return
else:
for c in range(0, n): # 新的一行可以选择放第(0, n)列
# c代表将要放置再第c列
if isValid(n, r, c, board):
# 放在第c列
temp = ""
for i in range(len(board[r])):
if i != c:
temp+= board[r][i]
else:
temp += "Q"
board[r] = temp
# 递归调用
backtrack(board, r+1)
# 撤销选择
temp = ""
for i in range(len(board[r])):
if i != c:
temp+= board[r][i]
else:
temp += "."
board[r] = temp
res = []
board = genBoard(n)
backtrack(board, 0)
return res
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
List<String> board = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++){
sb.append(".");
}
for (int i=0; i<n; i++){
board.add(sb.toString());
}
backtrack(res, board, n, 0);
return res;
}
public boolean isValid(List<String> board, int n, int r, int c){
// 是否有同一行的
String boardR = board.get(r);
if(boardR.contains("Q")) return false;
// 是否有同一列的
StringBuilder sbBoardC = new StringBuilder();
for(int i=0; i<n; i++){
sbBoardC.append(board.get(i).charAt(c));
}
if(sbBoardC.toString().contains("Q")) return false;
int tempR;
int tempC;
StringBuilder sb;
// 右下
tempR = r;
tempC = c;
sb = new StringBuilder();
while(tempR < n && tempC < n){
sb.append(board.get(tempR).charAt(tempC));
tempR ++;
tempC ++;
}
if(sb.toString().contains("Q")) return false;
// 左上
tempR = r;
tempC = c;
sb = new StringBuilder();
while(tempR >= 0 && tempC >= 0){
sb.append(board.get(tempR).charAt(tempC));
tempR --;
tempC --;
}
if(sb.toString().contains("Q")) return false;
// 右上
tempR = r;
tempC = c;
sb = new StringBuilder();
while(tempR >= 0 && tempC < n){
sb.append(board.get(tempR).charAt(tempC));
tempR --;
tempC ++;
}
if(sb.toString().contains("Q")) return false;
// 左下
tempR = r;
tempC = c;
sb = new StringBuilder();
while(tempR < n && tempC >= 0){
sb.append(board.get(tempR).charAt(tempC));
tempR ++;
tempC --;
}
if(sb.toString().contains("Q")) return false;
return true;
}
public void backtrack(List<List<String>> res, List<String> board, int n, int r){
// System.out.println(r);
if(r >= n){
// System.out.println(board);
List<String> boardCopy = new ArrayList<>(board);
res.add(boardCopy);
return;
}
// 确定行r之后可以选择任意一列
for(int c=0; c<n; c++){
// System.out.print("#");
// System.out.println(c);
if(isValid(board, n, r, c)){
// 在(r, c)位置放置一个棋子
char[] boardR = board.get(r).toCharArray();
boardR[c] = 'Q';
board.set(r, String.valueOf(boardR));
// System.out.print("%");
// System.out.println(r);
backtrack(res, board, n, r+1);
// 在(r, c)位置取消放置
boardR = board.get(r).toCharArray();
boardR[c] = '.';
board.set(r, String.valueOf(boardR));
}
}
}
}
单词搜索
leetcode 79
给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ] 给定 word = “ABCCED”, 返回 true 给定 word = “SEE”, 返回 true 给定 word = “ABCB”, 返回 false
import time
def func(board, word):
def backtrack(start_x, start_y, pos, visited):
# print(board[start_x][start_y], word[pos])
# start_x和start_y是搜索起点的坐标，pos是在word中当前搜索位置
if pos == len(word) - 1: # 递归终止的条件
# 如果pos指向word中的最后一个元素了（这时前面的肯定都已经满足了，要不然走不到这一步）
# 如果最后一位再满足的话，就是找到了，否则还是不行
return board[start_x][start_y] == word[pos]
elif board[start_x][start_y] == word[pos]:
# 如果还没搜到最后一位，但是当前的一位符合的话，就朝着接下来所有可能的方向搜索一遍
visited[start_x][start_y] = True # 做选择
choices = []
i, j = start_x, start_y
if 0 <= j - 1 < n and not visited[i][j-1]:
choices.append((i, j - 1))
if 0 <= i - 1 < m and not visited[i - 1][j]:
choices.append((i - 1, j))
if 0 <= j + 1 < n and not visited[i][j+1]:
choices.append((i, j + 1))
if 0 <= i + 1 < m and not visited[i+1][j]:
choices.append((i + 1, j))
for c in choices:
if backtrack(c[0], c[1], pos+1, visited):
return True
visited[start_x][start_y] = False # 撤销选择
else:
# 如果当前这一位都不一样的话，直接返回False
return False
m, n = len(board), len(board[0])
visited = [[False for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
# 对棋盘上的每一个格子都从头开始搜索，只要找到一个合适的，就返回真
print("before", visited)
if backtrack(i, j, 0, visited):
print("after", visited)
return True
# 如果对每一个都找一遍都没有，那就返回假
return False
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
if(m==1 && n==1){
return String.valueOf(board[m-1][n-1]).equals(word);
}
boolean[] exist = {false};
int[][] directions = {
{0, 1},
{1, 0},
{-1, 0},
{0, -1},
};
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
// System.out.println(i + ", " + j + " " + board[i][j]);
List<Character> path = new ArrayList<>();
if (!exist[0]){
boolean [][] visited = new boolean[m][n];
for(int k=0; k<m; k++){
for(int v=0; v<n; v++){
visited[k][v] = false;
}
}
backtrack(path, board, word, i, j, 0, visited, directions, exist);
}
}
}
return exist[0];
}
public boolean isValid(char[][] board, int m, int n){
if(m < 0 || n < 0){
return false;
}
if(m >= board.length){
return false;
}
if(n >= board[0].length){
return false;
}
return true;
}
public void backtrack(List<Character> path, char[][] board, String word, int startX, int startY, int pos, boolean[][] visited, int[][] directions, boolean[] exist){
if(exist[0] == true){
return;
}
// System.out.println(startX + "# " + startY);
if(board[startX][startY] != word.charAt(pos)){
exist[0] = false;
return;
} else if(pos == word.length()-1){
exist[0] = true;
return;
}
visited[startX][startY] = true;
for (int[] direction : directions) {
int m = startX + direction[0];
int n = startY + direction[1];
if (isValid(board, m, n) && !visited[m][n]) {
backtrack(path, board, word, m, n, pos+1, visited, directions, exist);
}
}
visited[startX][startY] = false;
}
}
