回溯法

[lovelmh13]

什么时候用回溯法

当看见题目中写着 1 <= nums.length <= 6 类似的很小的范围时（范围太大的话，超时超到爆），可能是因为复杂度很高，可以直接用回溯（穷举）法暴力破解。

当问所有的可能性的时候，可以使用回溯法。

回溯的基本框架

回溯法就是一个多枝树的递归

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

也不是必须这样写，不写 for ,只要让 backtrack 滚动起来，可以一直递归就行。

如果要求使用的数不重复，则先把数组排列好，按顺序搜索方便排除

出现在 leetcode 里字节前 100 道里的回溯相关的题：

参考：回溯算法详解