理论基础

• 回溯是一种纯暴力搜索的方法，它和递归相辅相成，通常是执行完递归之后紧接着执行回溯
• 相较于以往使用的for循环暴力搜索，回溯能解决更为复杂的问题，如以下的应用场景
• 应用场景
  • 组合问题
    • 如一个集合{1,2,3,4}，找出长度为2的组合
  • 排列问题
    • 相较于组合，排列是有顺序的，如{1,2}只有一种组合，但是有两种排列
  • 切割问题
    • 给一个字符串，给一个要求，求得怎么切割满足要求
  • 子集问题
    • 给一个集合，求它的子集
  • 棋盘问题
    • 如N皇后和解数独等
• 回溯法的思维结构——树型结构
  • 宽度代表集合的大小
  • 深度代表递归的深度
  • 

# 回溯编程模板
def backtracking(形参): # 返回值通常为空
    if (终止条件):
        存放结果
        return
        
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）):
        处理节点
        backtracking(路径，选择列表) # 递归
        回溯，撤销处理结果