本文目录
基本思想
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 使用回溯法解决问题的步骤如下：
- 针对所给问题，确定问题的解空间；
- 确定结点的扩展搜索规则；
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常见题目
括号生成
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(S, left, right):
if len(S) == 2*n:
res.append(S)
return
if left < n:
backtrack(S+'(', left+1, right)
if right < left:
backtrack(S+')', left, right+1)
backtrack("", 0, 0)
return res
子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.helper(nums, 0, [], res)
return res
def helper(self, nums, index, path, res):
res.append(path)
for i in range(index, len(nums)):
self.helper(nums, i+1, path+[nums[i]], res)
子集 II
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
self.dfs(nums, 0, [], res)
return res
def dfs(self, nums, index, path, res):
res.append(path)
for i in range(index, len(nums)):
if i > index and nums[i] == nums[i-1]:
continue
self.dfs(nums, i+1, path+[nums[i]], res
全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
self.helper(nums, [], res)
return res
def helper(self, nums, path, res):
if not nums:
res.append(path)
for i in range(len(nums)):
self.helper(nums[:i]+nums[i+1:], path+[nums[i]], res)
以nums=[1,2,3]为例可视化帮助理解：
dfs(nums = [1, 2, 3] , path = [] , result = [] )
|____ dfs(nums = [2, 3] , path = [1] , result = [] )
| |___dfs(nums = [3] , path = [1, 2] , result = [] )
| | |___dfs(nums = [] , path = [1, 2, 3] , result = [[1, 2, 3]] )
| |___dfs(nums = [2] , path = [1, 3] , result = [[1, 2, 3]] )
| |___dfs(nums = [] , path = [1, 3, 2] , result = [[1, 2, 3], [1, 3, 2]] )
|____ dfs(nums = [1, 3] , path = [2] , result = [[1, 2, 3], [1, 3, 2]] )
| |___dfs(nums = [3] , path = [2, 1] , result = [[1, 2, 3], [1, 3, 2]] )
| | |___dfs(nums = [] , path = [2, 1, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] )
| |___dfs(nums = [1] , path = [2, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] )
| |___dfs(nums = [] , path = [2, 3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
|____ dfs(nums = [1, 2] , path = [3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
|___dfs(nums = [2] , path = [3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
| |___dfs(nums = [] , path = [3, 1, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] )
|___dfs(nums = [1] , path = [3, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] )
|___dfs(nums = [] , path = [3, 2, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] )
全排列 II
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
组合总和
class Solution:
def combinationSum(
self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.dfs(candidates, target, 0, [], res)
return res
def dfs(self, nums, target, index, path, res):
if target == 0:
res.append(path)
return
for i in range(index, len(nums)):
if nums[i] > target:
break
self.dfs(nums, target-nums[i], i, path+[nums[i]], res)
组合总和 II
class Solution:
def combinationSum(
self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.dfs(candidates, target, 0, [], res)
return res
def dfs(self, nums, target, index, path, res):
if target == 0:
res.append(path)
return
for i in range(index, len(nums)):
if nums[i] > target:
break
self.dfs(nums, target-nums[i], i, path+[nums[i]], res)
单词搜索
class Solution:
def exist(self, board, word):
if not board:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.exist_helper(board, i, j, word):
return True
return False
# check whether can find word, start at (i,j) position
def exist_helper(self, board, i, j, word):
if len(word) == 0: # all the characters are checked
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[0] != board[i][j]:
return False
tmp = board[i][j] # first character is found, check the remaining part
board[i][j] = "#" # avoid visit agian
# check whether can find "word" along one direction
res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
board[i][j] = tmp
return res
N皇后
class Solution:
def solveNQueens(self, n: int):
res = []
self.helper(n, [], [], [], res)
return [["."*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in res]
def helper(self, n, queens, xy_dif, xy_sum, res):
rows = len(queens)
if rows == n:
res.append(queens)
return
# 若p + q == x + y 或者 p - q == x - y，说明点(p, q)和(x, y)在对角线上
for col in range(n):
if col not in queens and (rows-col) not in xy_dif \
and (rows+col) not in xy_sum:
self.helper(n, queens+[col], xy_dif +
[rows-col], xy_sum+[rows+col], res)
分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s:
return []
res = []
self.helper(s, [], res)
return res
def helper(self, s, split, res):
if s == "":
res.append(split)
return
for i in range(len(s)):
if s[:i+1] == s[i::-1]:
self.helper(s[i+1:], split+[s[:i+1]], res)