回溯算法(基于Python)
递归
递归(recursion)是一种算法策略，通过函数调用自身来解决问题。"递"指程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。"归"指触发终止条件后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。递归代码主要包含三个要素：
1. 终止条件：用于决定什么时候由“递”转“归”。递归的结束条件成为递归出口。
2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。
递归算法解题通常显得很简洁，但运行效率较低。因此，在使用递归算法时，需要特别注意递归出口的设计，以避免出现死循环或栈溢出等问题。
递归算法的一个简单例子：以计算一个函数 f 在 n 处的取值为例，假设有 f(n) = g(n,f(n-1))，则首先判断是否达到终止条件，达到则直接返回结果，否则返回g(n,f(n-1))，如计算 f(n) = 1 + 2 + ... + n：
def f(n):if n==1: # 终止条件return 1result = n + f(n-1) # 第n项和第n-1项的关系return result回溯
回溯是递归过程，算法程序的主体就是递归函数。回溯算法可以抽象为 n 叉树，叶子结点就是递归函数要收集的结果，对应终止条件，满足终止条件时应当 return 。下面是 for 循环，用于处理集合元素，for 循环内是处理节点、递归函数、回溯操作。一次回溯就相当于一次 for 循环。
回溯的三个要素：递归函数的参数、终止条件、当前操作和子问题。
结果录入程序写在哪：仅叶子结点记入结果(如46. 全排列)，则结果录入这一步放在终止条件成立时的程序内部，每个节点都记入结果(如78. 子集)，则结果录入这一步放在递归函数第一行(条件成立时的程序前面)。
当前步骤的操作执行后写递归子问题的语句，递归子问题的语句后面写回溯语句。
若 path 是列表则录入结果这一步中应将其写为 path.copy() (如46. 全排列)，其他地方写 path 。若 path 是字符串则递归函数内第一行写 nonlocal path (如22. 括号生成)，其他地方写 path 。回溯操作时数组写 path.pop() ，字符串写 path[0:len(path)-1] 。
LeetCode题目
由于回溯问题都可以抽象为 n 叉树，因此我们阶梯时先将问题对应的树画出来，再根据树的结构来写程序。
46. 全排列
题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。例如输入 nums = [1,2,3]，输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。
算法：以 nums = [1,2,3] 为例，其树形图如下
其中 () 表示已经选取的元素，[] 表示还原数组中还未被选取的元素，{} 表示原数组各位置的元素是否已被选取过。
用 used 表示上面的 {}，需要收集的结果是上图中的叶子结点 path 。因此终止条件达成时才会收集结果。
递归函数的输入参数： used 。
终止条件： path 的长度已经等于 nums 。
当前操作：本次选哪个数。
子问题：剩余的数组成的排列。
def permute(nums):result, path = [], []used_init = [0]*len(nums)def f(used):if len(path)==len(nums): # 终止条件result.append(path.copy())returnfor i in range(0,len(nums)): # 当前步骤操作if used[i]==1: # 跳过之前步骤选过的数字continueused[i] = 1 # 之前没选过的数字入选path.append(nums[i])f(used) # 递归path.pop() # 回溯used[i] = 0f(used_init)return resultcontinue 是避免一个元素被多次选入 path 中的情况，以树状图中的第一列第一层到第二层的过程为例，前面的步骤已经选过 1 了，则下面只能再选 2 和 3 ，若循环中遇到 1 则应当跳过本次迭代( i = 1 )而直接进入下面的迭代( i = 2,3 )。
注意程序中的回溯操作包含两行，分别是 path.pop() 和 used[i]=0。
在上述代码中，path.copy() 的使用是必要的，因为 Python 中的列表是可变对象。这意味着如果你直接将 path 列表添加到 result 列表中，那么当你后续修改 path 时，result 中已经添加的那些 path 列表的引用也会跟着改变，因为它们都指向同一个内存地址。为了避免这种情况，我们创建一个 path 列表的副本，并将其添加到 result 中。这样，即使后续修改了 path，result 中存储的副本也不会受到影响。
78. 子集
题目：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。例如输入 nums = [1,2,3]，输出[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。
算法：以 nums = [1,2,3] 为例，其树形图如下
需要收集的结果 path 是上图中的每个节点(不只是叶子结点)，终止条件未达成时也需要收集结果。
递归函数的输入参数：从哪一步开始(start)。
终止条件：开始的位置已经超出数组最后一位(start > len(nums)-1)。
当前操作：本次选哪个数。
子问题：从下一个位置开始能得到哪些子集。
path 从空集 {} 开始，备选元素集从 nums 开始，第 0 轮可取 1,2,3，递归函数中第一步就要加入 path 因为上图中的树没有加入空集的步骤，其每层生成的依次为大小 1,2,3 的子集。
start = 0 的时候输入 path = {} ，递归函数第一步 result.append(path.copy()) 会把 path 加入中 result，然后开始对其进行树的第一层操作，选取一个元素加入中 path，选择了 1 则下面一步的可选集合为 {2,3}，选择了 2 则下一步可选集合为 {3} (为了避免和前面一种情况重复因此不可再选 1)，选择了 3 则下一步可选集合为 {} (为了避免和前面一种情况重复因此不可再选 1和2)。下面两层的情况同理。path.pop() 的作用以第一列第二层为例，选了 2 得到 {1,2} 后再退回 {1} 才能再选 3 变成 {1,3} ，不退回则得到的是 {1,2,3}。
def subsets(nums):result, path = [], []def f(start):result.append(path.copy())if start == len(nums):return for i in range(start,len(nums)):path.append(nums[i])f(i+1)path.pop()f(0)return result17. 电话号码的字母组合
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
例如输入 '23' ，输出 ['ad','ae','af','bd','be','bf','cd','ce','cf'] 。
算法：以 digits = '23' 为例，其树形图如下
其中 () 表示已经选取的元素，[] 表示还原数组中还未被选取的元素。
用 index 表示遍历到了哪一位，需要收集的结果是上图中的叶子结点 path 。因此终止条件达成时才会收集结果。
递归函数的输入参数： index 。
终止条件： index 的长度已经等于 digits (最后一步是 index = len(digits)-1)
当前操作：本次选 index 对应数字的对应字母集的哪个字母。
子问题：剩余的数字的对应字母集的字母组合。
def letterCombinations(digits):dic = {2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'}result, path = [], ''def f(index):nonlocal pathif index == len(digits):result.append(path)returnletters = dic[int(digits[index])]for i in letters:path += i # 添加当前字符到路径中f(index + 1) # 递归调用，处理下一个数字path = path[0:(len(path)-1)] # 回溯，移除最后一个字符，尝试下一个可能的字符if digits: # 如果输入的数字字符串非空f(0)return result如果你在一个嵌套函数内部修改了一个在外部函数中定义的变量(path)，你需要确保这个变量在嵌套函数中被当作是非局部变量处理。这可以通过在嵌套函数内部使用 nonlocal 关键字来实现。
39. 组合总和
题目：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
例：输入 candidates = [2,3,5] ， target = 8 ，输出 [[2,2,2,2],[2,3,3],[3,5]] 。
算法：以 candidates = [2,3,5] ， target = 4 为例，其树形图如下
其中 {} 表示已经选取的元素，[] 表示还原数组中还未被选取的元素。
递归函数的输入参数： start 。
终止条件： sum(path)>target(此时直接返回)或sum(path)==target(此时将path加入结果再返回)
当前操作：本次选哪个数。
子问题：从本次选取数字开始到 candidates 结尾的数字的组合。
def combinationSum(candidates, target):result, path = [], []def f(start):if sum(path)>target:returnif sum(path)==target:result.append(path.copy())returnfor i in range(start, len(candidates)):path.append(candidates[i])f(i)path.pop()f(0)return result 22. 括号生成
题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。例如输入 n = 3 ，返回 n = ['((()))','(()())','(())()','()(())','()()()'] 。
算法：以 n = 2 为例，其树形图如下
递归函数的输入参数：左右括号的个数 n_left 和 n_right 。
终止条件： path长度已经达到2n。
当前操作：选左括号还是右括号。
子问题：后面剩余的括号怎么选。
需要注意的是左右括号的选择条件，当左右括号数量相同且左括号少于n个时只能选取左括号，当左括号已有n个时只能取右括号，当左括号数量大于右括号数量且左括号少于n个时可以选左括号或右括号。
def generateParenthesis(n):result, path = [], ''def f(num_left, num_right):nonlocal path # path为字符串时的必要步骤if len(path) == 2 * n: # 终止条件result.append(path)returnif num_left < n and num_left > num_right: # 可(可)的情况path += '('f(num_left + 1, num_right)path = path[0:len(path)-1]path += ')'f(num_left, num_right + 1)path = path[0:len(path)-1]if num_left < n and num_right == num_left: # 只可(的情况path += '('f(num_left + 1, num_right)path = path[0:len(path)-1]if num_left==n: # 只可)的情况path += ')'f(num_left, num_right + 1)path = path[0:len(path)-1]f(0, 0)return result131. 分割回文串
题目：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。例如输入 s = 'aab' 输出 [['a','a','b'],['aa','b']] 。
算法：以 s = 'aab' 为例，其树形图如下
递归函数的输入参数：开始切割的位置 start。
终止条件： 切割位置已经超出最大( start = len(s) )。
当前操作：选择一个大于等于 start 的位置切割。
子问题：后面剩余的部分怎么切割。
def partition(s):result, path = [], []def backtrack(start):if start == len(s):result.append(path.copy())returnfor i in range(start, len(s)):s_candidate = s[start:i+1]if s_candidate == s_candidate[::-1]: # 注意此处判断是否分割出回文子串path.append(s[start:i + 1])backtrack(i + 1)path.pop()backtrack(0)return result51. N皇后
题目：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
例：
算法：树形图第一层选择的是第一行放入棋子的位置，第二层选择第二行放入棋子的位置，以此类推。
递归函数的输入参数：要放置哪一行 row。
终止条件：放置位置已经超出最大( row = n )。
当前操作：选择在本行哪个位置放置棋子。
子问题：后面剩余的部分怎么切割。
def solveNQueens(n):result, path = [], [['.'] * n for _ in range(n)]def is_valid(path, row, col):for i in range(0,row):if path[i][col] == 'Q': # 检查列return 0for i in range(1,row+1):if col - i >= 0 and path[row-i][col-i] == 'Q': # 检查左上角return 0if col + i < n and path[row-i][col+i] == 'Q': # 检查右上角return 0return 1def f(row):if row == n:result.append([''.join(x) for x in path])returnfor col in range(n):if is_valid(path, row, col)==1:path[row][col] = 'Q'f(row + 1)path[row][col] = '.'f(0)return result