今日任务：

1. 回溯算法总结
2. LeetCode332 重新安排行程（没写）
3. LeetCode51 N皇后（没写）
4. LeetCode37 解数独（没写）

资料来源：

1. 代码随想录 | 回溯算法总结
2. 代码随想录 | LeetCode332 重新安排行程
3. 代码随想录 | LeetCode51 N皇后
4. 代码随想录 | LeetCode37 解数独

1 回溯算法总结

回溯算法最重要的就是如何将要解决的问题映射到那颗具体的回溯的树上去，比如说今天的332和37，一旦能想明白这一点，剩下的就不难了。

回溯算法模板：

def __init__():
    self.path = []
    self.result = []
    self.题目给定资料...
    
def 入口函数():
    self.题目给定资料赋值
    back_tracking()
    return self.result
    
def back_tracking():
    if 终止条件:
        self.result.append(self.path.copy())
    return
    
    for 单层递归循环
        if 符合条件:
            self.path.append()
            self.back_tracking()  向下递归
            self.path.pop()

回溯算法查重问题：

根据这几天的题来说，查重有两个问题：在哪里查？具体查谁？

1. 在哪里查？

   • 树枝查重：生效范围是所有的递归函数，需要在类变量里记录重复元素/下标
   • 树层查重：生效范围是同一层的所有递归函数，需要在上一层的递归函数中记录重复元素/下标或者对题目给定元素进行排序从而在循环中检查前后元素来查重
   • 递归查重：生效范围是单个递归函数内，需要在单个递归函数中记录重复元素/下标

   递归查重和树层查重本身是有相似性的，递归查重可以说就是树层查重另一个版本。但是为了分的清楚点还是分开讨论比较好。

2. 具体查谁？

   • 查元素是否重复：要记录的是元素本身，除了通过哈希数组num_used来记录该元素的值是否被用过以外，也可以对题目给定元素进行排序从而在循环中检查前后元素来查重
   • 查下标是否重复：要记录的是元素的位置，只能通过哈希数组index_used来记录该元素是否被用过

回溯算法参数加不加start_index？

分情况讨论。如果下一层递归的循环需要从上一层指定位置开始，就需要start_index参数；如果下一层递归的循环可以从头开始/开始位置不和上一层递归有所关联，那么就不需要start_index参数。