写在前面：本文的一些定义不一定是对的，我就是把我的思路写出来了。

递归一般是和树紧密相连的。回溯也可以认为是在树形结构中进行的。

回溯就是递归触底了然后向上返。同时在向上返的过程中要注意「恢复状态」。不能说返回到上一级了，状态还是当前层级的。

回溯问题一般和排列、组合问题关系比较密切。排列、组合需要枚举所有的可能性，枚举的过程就可以画出一棵树形图，然后在树里边选择符合题意的。因此解答回溯问题一般都是建议要先画出树形图。

画好树形图，就可以写代码了。

下面总结了几个技巧：

  • 大概的框架：

这题是 39 号问题，这里只用来说明一般的代码框架。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 一般都会用到这两个变量，ans 存放最终答案，curAns 存放当前答案
        // 存放当前答案的 curAns 也不一定是一个，也可能是多个。比如二进制手表问题
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curAns = new ArrayList<>();

        dfs(candidates, target, 0, ans, curAns);

        return ans;
    }

    /*
    * candidates 和 target 是题目给定的
    * idx 是用来控制下层递归的开始位置的。这个参数比较多变
    * ans 和 curAns 是用来保存答案的
    * */
    private void dfs(int[] candidates, int target, int idx, List<List<Integer>> ans, List<Integer> curAns) {
        // 在什么条件下就不继续走了
        if (target < 0) return;

        // 在什么条件下需要将 curAns 存入到 ans
        // 也有的题目不需要这个 if，只要见到 curAns 就存到 ans 里面。比如子集问题
        if (target == 0) {
            ans.add(new ArrayList<>(curAns));

            return;
        }

        // 一般都有这层循环，循环整个给定的数组，还是只循环 idx 之后的部分要根据题目来
        for (int i = idx; i < candidates.length; i++) {
            // 这里可以进行一些「剪枝」操作。根据树形图来想
            // break、continue、return 都可以用来剪枝，但是具体的要根据题目来
            if (target - candidates[i] < 0) continue;
            
            // 将当前的内容加到 curAns
            curAns.add(candidates[i]);
            
            // 递归调用
            dfs(candidates, target - candidates[i], i, ans, curAns);

            // 「恢复状态」。递归之前改了什么，这里就再改回来
            curAns.remove(curAns.size() - 1);
        }
    }
  • 如果题目给的数据有重复元素，那么一般的做法是：
  1. 将给定的数组排序
  2. 在递归函数里用这句话处理重复元素：if (i > idx && nums[i] == nums[i - 1]) continue;。这样可以省略掉 used 数组，如果想用 used 数组的话，这样处理重复元素：if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;。注意这两种方式的 i 条件不一样，一个是 i>idx 一个是 i>0。