回溯实际上就是遍历的变种，不符合条件时，本次遍历向上回退。一般来说，回溯算法都可以将决策路径画成树的形状，成为一棵搜索树。回溯法执行的过程实际上就是在这棵树上做遍历。使用回溯法的题目，为什么不能用递归法，因为回溯法中记录路径的栈只有一个。

1、回溯算法的基本思想

    回溯算法的定义：回溯法采用试错的思想，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。—— 回溯法 - 维基百科[3]

    从字面意思上来看，回溯（backtracking） 实际上就是“撤回一步”的意思。而在二叉树的 DFS 遍历中，从一个结点退出就是一种回溯。回溯法和 DFS 是息息相关的。

    根据回溯操作的特性，我们使用栈记录遍历时的当前路径。当进入一个结点时，做 push 操作；当退出一个结点时，做 pop 操作，进行回溯。

2、案例1

    给定一个二叉树和一个目标和，找到所有从根结点到叶结点的路径，使得路径上所有结点值相加等于目标和。

public List<List<Integer>> pathSum(TreeNode root, int sum) {

    List<List<Integer>> res = new ArrayList<>();

    Deque<Integer> path = new ArrayDeque<>();

    traverse(root, sum, path, res);

    return res;

}

void traverse(TreeNode root, int sum, Deque<Integer> path, List<List<Integer>> res) {

    if (root == null) {

        return;

    }

    path.addLast(root.val);

    if (root.left == null && root.right == null) {

        if (root.val == sum) {

            res.add(new ArrayList<>(path));

        }

    }

    int target = sum - root.val;

    traverse(root.left, target, path, res);

    traverse(root.right, target, path, res);

    path.removeLast();

}

    代码的整体结构和上期例题题解类似，只是加上了栈 path 记录当前路径。关于栈的 push 和 pop 操作，有两个需要注意的地方：

            * 保证刚进入结点就 push，最后退出结点之前才 pop，这样才能使当前路径和遍历的进度对应；

            * 在叶结点判断后，不能进行 return，否则会跳过后面的 pop 操作而出错。

    这两点都需要做题来体验，建议亲自做一遍例题来体会。

3、案例2

    题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

    Subsets 问题就是要枚举出集合的所有子集。生成子集有一个很简单的策略，一个子集可以选择使用或不使用第一个元素，选好之后，再对第二个元素进行选择，以此类推。这就是一种回溯的思想。这又是一个树的结构。一般来说，回溯算法都可以将决策路径画成树的形状，成为一棵搜索树。回溯法执行的过程实际上就是在这棵树上做遍历。刚好这还是一棵二叉树，这又联系上了二叉树的遍历。

    那么，我们可以尝试用遍历树的思路写出回溯法的代码。这里的栈是当前子集里的元素，push 操作是往子集里加元素，pop 操作是从子集中删除元素（撤销选择）。

    最终我们得到完整的代码：

public List<List<Integer>> subsets(int[] nums) {

    Deque<Integer> current = new ArrayDeque<>(nums.length);

    List<List<Integer>> res = new ArrayList<>();

    backtrack(nums, 0, current, res);

    return res;

}

void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {

    if (k == nums.length) {

        res.add(new ArrayList<>(current));

        return;

    }

    // 不选择第 k 个元素

    backtrack(nums, k+1, current, res);

    // 选择第 k 个元素

    current.addLast(nums[k]);

    backtrack(nums, k+1, current, res);

    current.removeLast();

}

    这份代码看起来和 Path Sum II 的代码非常类似，例如都使用了一个栈，递归的参数也很像。但是递归调用和 push/pop 的操作方式有一些微妙的地方。

    现在，我们是在调用递归函数之前和之后进行 push/pop，这是因为数组本身并没有递归结构，我们需要用 push/pop 操作来营造出不同的选择。两个递归函数的调用其实都是一样的，但因为 current 中的内容不一样，所以其实是两个决策路径。

4、时间复杂度

    回溯算法的复杂度一般都会很高。以 Subsets 问题为例，从搜索树的规模可以看出算法的时间复杂度是非常高的 。不过，回溯法写成这样的复杂度是可接受的，一般的回溯法题目也没有更高效的解法。

5、总结

    通过这两个例题我们看到了回溯算法和二叉树遍历的相似关系。在求解回溯算法的时候，我们可以先构造一个搜索树，在这个树上遍历进行递归求解。

    需要注意的是，例题 Subsets 中的搜索树是二叉树，这只是个巧合。实际上搜索树完全可以是多叉树，而且多叉树才更常见。

    本篇讲解的是比较基础的回溯法思想。回溯法还有很多技巧，例如 Permutation 和 Combination 系列题目，后续还会有文章进行讲解。

6、相关题目

    二叉树遍历的题目（理解遍历思想）：

            * 129 - Sum Root to Leaf Numbers[4]

            * 257 - Binary Tree Paths[5]

    回溯法题目（这里只列出比较简单的两道，更多的题目可以在 LeetCode 上寻找 backtracking 标签）：

            * 22 - Generate Parentheses[6]

            * 39 - Combination Sum[7]