数据结构和算法--回溯法
回溯算法
定义：回溯算法，又称“试探法”。解决问题时， 每一步都是尝试态度，如果发现并不是好的，
或者这么走下去很定达不到目标，立刻返回重新操作， 这种走不通就回退的方法为回溯算法。
解题一般步骤：
1、定义一个解空间， 它包含问题的解；
2、利用适合的方法组织空间解；
3、利用深度优先法搜索解空间；
4、利用界限函数避免移动到不可能产生解的子空间。
详细描述：
回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当
算法搜索至解空间树的某一节点时，先利用 剪枝函数 判断该节点是否可行（即能得
到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否
则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：
- 使用约束函数，剪去不满足约束条件的路径；
2.使用限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。
解空间树分为两种：子集树和排列树。 两种在算法结构和思路上大体相同。
应用：
当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。
它有“通用解题法”之美誉。
回溯 vs 递归
很多人认为 回溯 和 递归 是一样的， 其实不然。回归中可以看到递归的影子
但是两者是有区别的。
回溯： 从问题本身出发，寻找可能实现的所有可能情况。和
穷举法的思想相近，不同于穷举法是将所有的情况列举出来以后在一一筛选，而回溯法是在列举
过程中，如果发现当前情况不对，就停止后续工作，返回上一步，进行新的尝试。
递归： 是从问题的结果出发，例如求n！的结果，就需要知道
n(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)(n-2)!。这样不断地向
自己提问，不断地调用自己的思想就是递归。
两者联系： 回溯可以用递归思想实现
实现过程：
使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。例如，在解决列举集合{1,2,3}
所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：
回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的
答案。图 1 中的状态树是满二叉树，得到的叶子结点全部都是问题的解。
在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，
有时会发现此种情况下，再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，
就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。
回溯通模板
res = []
def backtrack(路径, 选择列表):
if 满足结束条件:
res.append(路径)
return
if 满足减枝条件:
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
实例：
力扣22题： 括号生成
数据n表示生成括号的对数，设计一个函数，用于生成所有可能， 并且有效的括号。
class Solution:
def __init__(self) -> None:
pass
def get_ass(self, n):
"""
:param n: 括号的对数
:return lis: 所有有效的括号组合
"""
lis = []
def backTrack(s: list, left: int, right: int):
if len(s) == 2 * n:
lis.append(''.join(s))
return
if left < n:
s.append('(')
backTrack(s, left + 1, right)
s.pop()
if right < left:
s.append(')')
backTrack(s, left, right + 1)
s.pop() # 每次调用回调函数之后，删除最后一个元素
backTrack([], 0, 0)
return lis
if __name__ == '__main__':
s = Solution()
res = s.get_ass(4)
print(res)
结果：
['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']
过程分析：
首先，从左括号开始，在条件 left < n的条件下，一直递归(即，树的深度优选策略)
直到条件不满足树的减枝，并且回退到上一步， 然后执行right < left 的条件，
并且递归运行，一直递归到最后得到所有符合括号。