代码框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        dfs(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

注意关注何为本层节点，指搜索树的孩子节点会是什么，有的是下一个元素是否要取（就两种），有的是下一个元素要取什么（那要列举后面的所有元素），还可能是图论里面下一步去哪，那可能需要遍历整个图。

变式

单纯的回溯法，一方面时间复杂度较高，需要试图剪枝。另一方面是可能会有对答案去重的需求，在此特别讨论。

剪枝

记忆化搜索

可以把之前已经计算出的答案记录到一个数组里面，这样后面如果要用的话，就可以直接取出来，不必再搜索一遍。

排序

有时只需要一个解便可退出循环，此时不同的搜索顺序可能对时间影响会很大。比方类似背包，确定要拿多少东西，我们从大的拿，放不下就可以直接剪枝了，可以节省时间。

前缀和剪枝

可以用这种方法，判断说是不是后面所有元素都加上也不够（或者刚好），那么就不必再往后搜索。

去重

set

第一种方法就是把所有答案先放入一个set中，等遍历结束，再把所有答案放回到数组。

记录每一个位置的元素是否被使用

先对序列排个序

若遇到了与上一个元素相同的元素，只有在前一个元素被使用了的时候，才可以使用它。这样搜索出来的结果就不会有重复的了。

记录一层内每一个数是否有被用过

这种在答案序列有序的情况下是比较好用的（递增子序列）

注意如果有负数的话数组下标要相应变化，或者变成map。

与动态规划的对比

其实回溯法遇到的一些问题和背包问题是非常类似的，都是解决每一个物体要或者不要的问题，那么在遇到这类问题的时候该如何选择方法呢？

dp的优势在时间，用$n^2$的时间即可完成，但是他的数组需要开到和背包容量一样大。因此在背包容量、单个物体体积的情况下可能会空间爆炸。

相比之下回溯法对空间的需求就没有这么大，但是时间耗费较大。

因此在n较小（30左右），且目标总和很大（比如到2e9），使用回溯

n较大（1000）使用dp。