09-回溯

总结

回溯法核心模板

回溯穷举核心思想

三大元素

路径：已做出的历史选择。
选择列表：当前这一步还可以怎么走。
结束条件：什么时候停下来。

撤销选择

回到上一个分叉口，尝试其他可能。

剪枝

明显已不满足条件，砍掉错误决策分支。

python

# 伪代码模板
def backtrack(路径, 选择列表):
    if 满足结束条件:
        保存结果
        return
    
    for 选择 in 选择列表:
        # 1. 做选择
        将选择加入路径
        更新选择列表
        
        # 2. 进入下一层决策树（递归）
        backtrack(路径, 剩下的选择列表)
        
        # 3. 撤销选择（回溯）
        将选择从路径中移除
        恢复选择列表

题目

01-46-全排列

leetcode-46，leetcode-47

输入：不重复 数组nums ，或重复数字
输出：可能的所有全排列

回溯全排列

定义res, path 当前路径, used 已使用数字
backtrack 回溯函数
- 结束条件：所有数字已用完，len(path) == len(nums)
  - 保存结果，res.append(path[:])，复制整份
- 遍历所有候选列表 (num not in used)
  - 选择当前值
  - 递归DFS向下查找
  - 撤销当前选择
开始回溯 backtrack() 更新res

python

def permute_dfs_backtrack(self, nums: List[int]) -> List[List[int]]:
    """ 数字不重复，输出所有可能性。通过dfs回溯，来进行寻找所有答案
    """
    # 所有排列结果
    res = []
    # 当前路径
    path = []
    # 哪些数字已经使用，避免重复选取
    used = set()

    def backtrack():
        # 结束条件
        if len(path) == len(nums):
          	# 注意：Python中列表是引用传递，需要加上 [:] 拷贝一份当前的值
            res.append(path[:])  
            return
        # 遍历所有候选列表
        for num in nums:
            if num in used:
                continue
            # 选择当前节点
            path.append(num)
            used.add(num)
            # 回溯
            backtrack()
            # 撤销当前选择
            path.pop()
            used.remove(num)
    backtrack()
    return res

重复数组全排列

重复数字全排列

示例

输入：[1, 1, 2]
输出：[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

核心思路

位置bool：判断数字是否使用。因为有重复，不能用set
对nums排序：相同数字 相邻。
候选列表过滤：当前数字和上个数字 相同，且上一个数字未被使用 (刚被释放)。
- nums[i] == nums[i-1] and used[i-1] == False

python

def permute_repeatnums_dfs_backtrack(self, nums: List[int]) -> List[List[int]]:
    """ 数字可能重复，输出全部可能的全排列答案 """
    # 最终结果
    res = []
    # 当前路径
    path = []
    # 各位置数字是否使用
    used = [False] * len(nums)

    # 排序，相同数字相邻
    nums.sort()

    def backtrack():
        # 终止条件
        if len(path) == len(nums):
            res.append(path[:])
            return

        # 遍历候选列表
        for i in range(len(nums)):
            if used[i]:
                # 当前数字已在路径中
                continue 
            # 剪枝，当前数字和上一个数字相同，且上一个数刚刚被撤销
            if i > 0 and nums[i] == nums[i-1] and used[i-1] == False :  
                continue
            # 选择当前值
            path.append(nums[i])
            used[i] = True
            backtrack()

            # 撤销当前选择
            path.pop()
            used[i] = False 

    backtrack()
    return res

02-78-子集

leetcode-78

输入：不重复 nums
输出：所有可能的子集，包含空集

子集和全排列

结果保存

全排列：走到叶子节点 才存储结果。
子集：每一步 都需要存储结果。空、单、部分、全部数字都是子集。

防重复方式

全排列：[1, 2]和[2, 1]是不同path。顺序 很重要。
子集：{1, 2}和{2, 1} 是相同集合。顺序 不重要。
子集 start_index：为了防{2,1}倒退，规定只能从start_index开始往后看。

start_indexDFS子集

带start_index的回溯

子集：每次进入backtrack都 保存结果
从start_index往后 遍历候选列表
- 选择：path保存nums[i]
- 递归进入下一层：backtrack(i+1)
- 回溯：path删掉nums[i]

python

def subsets_dfs_backtrack(self, nums: List[int]) -> List[List[int]]:
    """找出所有子集，数组不重复, dfs start_index"""

    res = []
    path = []

    def backtrack(start_index):
        # 存储当前内容
        res.append(path[:]) 
        # 依次遍历当前候选列表
        for i in range(start_index, len(nums)):
            # 选择当前值
            path.append(nums[i])
            # 递归进入下一层
            backtrack(i+1)
            # 回溯
            path.pop()

    backtrack(0)
    return res

重复数组子集

leetcode-90

数组有重复元素
[1, 2, 2]: [[],[1],[1,2],[1,2,2],[2],[2,2]]

核心思想

先对数组排序，相同元素 挨着。
使用used 记录数字是否已使用。
候选遍历时，若当前数字在上一轮刚作为候选项 遍历过，则跳过。

python

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    """ 数组有重复元素，输出不同子集。 排序+used
    """

    res = []
    path = []
    used = [False] * len(nums)

    nums.sort()

    def backtrack(start_index): 
        # 进入则保存结果
        res.append(path[:])

        # 遍历候选项
        for i in range(start_index, len(nums)):
            # 如果当前数字，上一轮刚刚使用过，则跳过
            if i > 0 and nums[i] == nums[i-1] and used[i-1] == False:  
                continue

            # 选择当前数字
            path.append(nums[i])
            used[i] = True
            # DFS搜索下一层
            backtrack(i+1) 
            # 回溯当前值
            path.pop()
            used[i] = False

    backtrack(0) 

    return res

03-17-电话号码的字母组合

leetcode-017

输入：仅包含2-9的字符串
电话号码：2-abc, 3-def, 4-ghi, 5-jkl, 6-mna, 7-pqrs, 8-tuv, 9-wxyz
输出：能表示的所有字母组合
示例
- 2：[a, b, c]
- 23：[ad,ae,af, bd, be, bf, cd, ce, cf]

特点

每一步，在不同的集合里取挑选字母。
- 全排列，子集：每一步是相同的集合
Step1: [a, b, c]，Step2: [d, e, f]

每步不同集合全排列思想

笔记

DFS 全排列思想

建立{数字-字母集合} 映射，每1步在特定集合里做选择。
终止条件：数字用完，保存结果。
候选列表：根据层数，选特定集合。

python

def letterCombinations(self, digits: str) -> List[str]:
    """DFS，回溯， 每一层取不同的集合"""

    if not digits:
        return []

    res = []
    path = []
    nums = [int(n) for n in digits]

    num2chars = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    }

    def backtrack(start_index):
        if start_index == len(nums):
            res.append("".join(path))
            return

        num = nums[start_index]
        choices = num2chars[num]  

        for ch in choices:
            path.append(ch)
            backtrack(start_index+1)
            path.pop()
    backtrack(0)

    return res

04-39-组合总和

leetcode-39

输入：无重复元素的数组 + 目标整数target
目标：从数组中找出和为target的所有不同组合，数字可重复使用。
输出：组合

注意

数字 可重复使用，同一位置数字可多次重复使用。

DFS回溯数字求和

核心思想

先做排序，方便剪枝。
backtrack(start_index)
终止条件：当前求和为target
候选列表：从start_index往后的所有数字
下一层回溯：传入i，而非i+1，依然可以选择当前数字
剪枝：当前和+candidates[i] >target

关键点

从小到大排序，方便做剪枝
同子集，都是组合问题，顺序不重要，所以需使用 start_index 来防止倒车。
- [2, 2, 3] 和 [3, 2, 2] 算一个答案
数字可重复选取：传给下一层索引是i，而非i+1
backtrack传入start_index和current_sum
剪枝：current_sum + current_val > target，则直接break，后续数字不用看了

python

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """排序+dfs+剪枝"""
    if not candidates:
        return []

    res = []
    path = []

    # 从小到大排序，为了后续能用 break 极速剪枝
    candidates.sort() 

    # 推荐将 current_sum 作为参数传入，避免 nonlocal 作用域问题
    def backtrack(start_index, current_sum): 
        # 找到合法组合
        if current_sum == target:
            res.append(path[:])
            return

        # 其实有了下面的 break 剪枝，这个判断甚至可以省略，但保留着逻辑更严密
        if current_sum > target:
            return
				# 遍历候选项
        for i in range(start_index, len(candidates)):
            current_val = candidates[i]

            # 终极剪枝：因为已经排序，当前超出 target，后面的必定超，直接 break！
            if current_sum + current_val > target:
                break  # 注意这里改成了 break

            # 1. 做选择
            current_sum += current_val
            path.append(current_val)

            # 2. 回溯，依然可以选择当前 i，不往回头选
            backtrack(i, current_sum)  

            # 3. 撤销选择
            path.pop()
            current_sum -= current_val

    # 初始 start_index=0, current_sum=0
    backtrack(0, 0)
    return res

05-22-括号生成

leetcode-22

输入：n，即n个左括号+n个右括号。
输出：所有可能生成的有效括号组合
示例：
- 3：["((()))", "(()())", "(())()", "()(())", "()()()"]
- 1： ["()"]

约束

必须生成合法括号

回溯法和括号合法性剪枝

backtrack(left_cnt, right_cnt)：传入左右括号数量
路径：每一步选择的 左或右括号
结束条件：路径长度==2n
候选列表：
- 选择左括号：left < n，最多n个左括号
- 选择右括号：right < left，左括号数量 < 右括号数量

python

def generateParenthesis(self, n: int) -> List[str]:

    if n <= 0:
        return []

    res = []
    path = []

    # 回溯，传入左右括号数量，方便剪枝
    def backtrack(left_cnt, right_cnt):
        # 结束条件
        if left_cnt + right_cnt == 2*n:
            res.append("".join(path))

        # 候选列表，选左括号 或 右括号
        for ch in ('(', ')'):
            if ch == '(':
                # 选左括号，最多选择n个左括号
                if left_cnt < n:  
                    path.append(ch)
                    backtrack(left_cnt+1, right_cnt)
                    path.pop()
            if ch == ')':
                # 选右括号，最多选择n个右括号，且右括号必须<左括号数量
                if right_cnt < left_cnt:  
                    path.append(ch)
                    backtrack(left_cnt, right_cnt+1)
                    path.pop()

    backtrack(0, 0)
    return res

06-79-单词搜索

leetcode-79

输入：m*n 字母矩阵，单词word
目标：字母可上下左右移动，判断word是否在矩阵中
输出：True, False

Path回溯搜索

DFS 搜索

核心思想

遍历每个ch，当ch和单词首字符相等时，进行dfs搜索。
dfs搜索：
- 终止条件：path长度和word相同
- 候选列表：上下左右 4个方向
- 选择条件：位置合法、位置未被使用、字符相同

python

def exist(self, board: List[List[str]], word: str) -> bool:
    """遍历首字符，相同则 dfs 上下左右搜索"""
    if not board or not word:
        return False

    m, n = len(board), len(board[0])

    used = [[False] * n for _ in range(m)]
    path = []

    valid_paths = []

    def backtrack(i, j):
        # 终止条件：单词已经拼凑弃权
        if len(path) == len(word):
            valid_paths.append(path[:])
            return

        # 找到1个就不找了，如果要找所有的，则注释掉
        if valid_paths:
            return

        # 下一个需要的字符
        wpos = len(path)
        need_ch = word[wpos]

        # 四个方向，候选项
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for di, dj in directions:
            # 新的候选 i, j
            ni, nj = i + di, j + dj
            # 超出范围
            if not 0 <= ni < m or not 0 <= nj < n:
                continue
            # 字符不相同，或者该位置已被使用
            if board[ni][nj] != need_ch or used[ni][nj]:
                continue
            # 选择当前位置，进行下一层回溯寻找
            path.append((ni, nj))
            used[ni][nj] = True
            backtrack(ni, nj)
            path.pop()
            used[ni][nj] = False
        return


    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                path.append([i,j])
                used[i][j] = True
                backtrack(i, j)
                path.pop()
                used[i][j] = False

    if len(valid_paths) > 0:
        return True
    return False

剪枝原地改变回溯搜索

剪枝原地改变DFS搜索

剪枝：矩阵不同字母数量 < 单词不同字母数量
搜索：正序搜索 首字母少或 逆序搜索 尾字母少
backtrack(i, j, k)：返回bool
- 终止：k == len(word)，[i,j]越界、字符不等。
- [i, j] 变为 #，表示used
- 上下左右 去回溯
- [i, j] 变回 原ch

python

def exist_pruning_backtrack(self, board: List[List[str]], word: str) -> bool:
    """剪枝，优化正序逆序查找，标准backtrack写法"""

    if not board or not word:
        return False

    m, n = len(board), len(board[0])

    # board和单词的字母统计
    board_counter = Counter([ch for row in board for ch in row])
    word_counter = Counter(word)

    # 剪枝，单词字母，不在矩阵中
    for ch, cnt in word_counter.items():
        if ch not in board_counter:
            return False

    # 尾字符比首字符在矩阵中的次数更少，翻转搜索效率更高
    if board_counter[word[-1]] < board_counter[word[0]]:
        word = word[::-1]

    def backtrack(i, j, k):
        # 找到目标单词，匹配成功
        if k == len(word):
            return True

        # ij越界、字符不匹配，则返回
        if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k]:
            return False

        # 选择当前位置i,j，设置为其他字符，进行上下左右搜索
        raw_ch = board[i][j]
        board[i][j] = "#"

        # 上下左右回溯，使用or，若有1个成功，则不进行下一个搜索
        res = backtrack(i+1, j, k+1) or backtrack(i-1, j, k+1) or backtrack(i, j+1, k+1) or backtrack(i, j-1, k+1)

        # 还原当前ij
        board[i][j] = raw_ch

        return res

    # 遍历每个字符，若和首字符相同，则进行回溯搜索
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                # 相同才进行回溯
                if backtrack(i, j, 0):
                    return True

    return False

07-131-分割回文串

leetcode-131

输入：字符串s
目标：把s分割成多个子串，使每个子串都是回文串
输出：所有分割方案。
示例：
- aab：[[a, a, b], [aa, b]]

切分回文回溯

backtrack()：不能往回头看，需使用start_index
路径：在哪些位置做切分
终止条件：start_index == len(s)
候选列表：start_index <= i < len(s)
- 选择条件：子串 s[start_index:i+1] 是回文字符串
- 回文子串判断：s == s[::-1]

python

def partition(self, s: str) -> List[List[str]]:
    """分割回文字符串"""
    if not s:
        return []

    res = []
    path = []

    def backtrack(start_index):

        # 终止条件，全部分割完成
        if start_index == len(s):
            res.append(path[:])
            return

        # 候选项分割项
        for i in range(start_index, len(s)):
            # 当前切割子串
            sub = s[start_index:i+1]
            # 子串不是回文串，说明当前切分位置不行
            if sub != sub[::-1]:
                continue

            # 1. 存储当前分割结果
            path.append(sub)
            # 2. 递归，从下一个位置i+1继续切分
            backtrack(i+1)
            # 3. 取消当前分割点，下一轮尝试切分更长子串
            path.pop()
        return

    backtrack(0)
    return res

08-51-N皇后

leetcode-51

输入：n
目标：把n个皇后，放在n*n的棋盘上，使皇后不能相互攻击。行、列、斜 都可攻击。
输出：所有的 棋盘放置方案，Q代表皇后，.代表空位。
示例：4，[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

[i,j] 可攻击范围

同行可攻击：used[i][*]
同列可攻击：used[*][j]
右斜可攻击：[i+1][j+1]、[i+2][j+2]
左斜可攻击：[i+1][j-1]、[i+2][j-2]

回溯主对角线判断方法

笔记

三大攻击

垂直攻击，右斜攻击(主对角线)，左斜攻击(副对角线)
主对角线： row-col 不变，如00, 11, 22
副对角线：row+col 不变，如02, 11, 20
垂直攻击：col 不能重复使用

python

def solveNQueens_colrowset(self, n: int) -> List[List[str]]:
    """回溯法，三大攻击：垂直攻击，右斜攻击(主对角线)，左斜攻击(副对角线)
        主对角线：00, 11, 22, row-col 不变
        副对角线：02, 11, 20, row+col 不变
    """
    # 结果和单次路径
    res = []
    # 记录 每一行选择的皇后所在列
    path = []

    # 三大攻击的set
    cols = set()
    # 主对角线：值
    diag1 = set()
    # 副对角线：值
    diag2 = set()

    def backtrack(row):
        # 递归终止条件
        if len(path) == n:
            board = []
            for col in path:
                raw_str = "." * col + "Q" + "." * (n-col-1)
                board.append(raw_str)
            res.append(board)
            return

        # 筛选候选列
        for col in range(n):
            if col in cols or col-row in diag1 or col+row in diag2: 
                # 当前列已使用，或在某主对角线(右斜)、在某副对角线(左斜)
                continue 
            # 选择col列
            path.append(col)
            cols.add(col)
            diag1.add(col-row)
            diag2.add(col+row) 
            # 回溯查找下一层
            backtrack(row+1)
            # 还原当前col的选择
            path.pop()
            cols.remove(col)
            diag1.remove(col-row)
            diag2.remove(col+row)

    backtrack(0)

    return res

回溯双层循环判断方法

回溯选择放置列n皇后

路径：每一行，皇后放在哪一列。
终止条件：len(path) == n
候选列表：当前行放在哪一列，必须满足当前条件。
递归选择下一行：

python

def solveNQueens_forpath(self, n: int) -> List[List[str]]:
    """回溯法，选择每一行把皇后放在哪一列，解决N皇后放置问题"""

    res = []
    path = []

    def backtrack(row):
        """回溯处理第row行"""

        # 回溯终止条件：path已装满
        if len(path) == n:
            res_p = ["".join(r) for r in path]
            res.append(res_p)
            return

        # 根据当前path，确定当前行的候选项，可以放置哪些列

        # 初始选项
        choices = [col for col in range(n)]
        for i, cols in enumerate(path):
            for j, value in enumerate(cols):
                if value == "Q":
                    # q_postions.append([i, j])
                    # 1. 垂直攻击
                    if j in choices:
                        choices.remove(j) 
                    # 2. 右斜攻击
                    rnj = j + (i - row)
                    if 0 <= rnj < n and rnj in choices:
                        choices.remove(rnj) 
                    # 3. 左斜攻击
                    lnj = j - (i - row)
                    if 0 <= lnj < n and lnj in choices:
                        choices.remove(lnj) 

        # 从候选项中，依次选择第c列，做选择
        for j in choices:
            cur_row_s = ["."] * n 
            cur_row_s[j] = "Q"
            path.append(cur_row_s)
            backtrack(row+1)
            path.pop()


    backtrack(0)

    return res

总结 ​

回溯法核心模板 ​

题目 ​

01-46-全排列 ​

回溯全排列 ​

重复数组全排列 ​

02-78-子集 ​

子集和全排列 ​

start_indexDFS子集 ​

重复数组子集 ​

03-17-电话号码的字母组合 ​

每步不同集合全排列思想 ​

04-39-组合总和 ​

DFS回溯 数字求和 ​

05-22-括号生成 ​

回溯法和括号合法性剪枝 ​

06-79-单词搜索 ​

Path回溯搜索 ​

剪枝原地改变回溯搜索 ​

07-131-分割回文串 ​

切分回文回溯 ​

08-51-N皇后 ​

回溯主对角线判断方法 ​

回溯双层循环判断方法 ​

总结

回溯法核心模板

题目

01-46-全排列

回溯全排列

重复数组全排列

02-78-子集

子集和全排列

start_indexDFS子集

重复数组子集

03-17-电话号码的字母组合

每步不同集合全排列思想

04-39-组合总和

DFS回溯数字求和

05-22-括号生成

回溯法和括号合法性剪枝

06-79-单词搜索

Path回溯搜索

剪枝原地改变回溯搜索

07-131-分割回文串

切分回文回溯

08-51-N皇后

回溯主对角线判断方法

回溯双层循环判断方法