博客

首先回溯法是深度搜索（DFS）的一种，即把所有可能穷举，根据条件筛选出符合条件的路径。

回溯法模板格式

dfs(...){
//根据递归终止条件进行筛选
if(符合需要的条件){
存储合理路径
return ...;
}
//对可能路径进行遍历
for(int i=起始条件；i<极限边界;i++){
向路径便令中添加元素
//进行下一轮搜索
def(...);
//深度优化的回头
...removeLast();
}
return ...;
}

下面举一个leetCode上的题目：

给出正整数n,k,求出1,2,3,4…n;求出所有含k个数字且无重复的全部结果。（题目大致是这样的）

用回溯法的解决如下：

public class Backtrack {
    private static Backtrack test;

    public static void main(String[] args) {
        int k = 3;
        int n = 5;
        shen = new Backtrack2();
        test.cobine(n, k);
    }
    public List<List<Integer>> cobine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
//        创建一个list记录搜索路径
        List<Integer> path = new ArrayList<>();
        dfs(n, k, 1, path, res);
        return res;
    }
    public List<List<Integer>> dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
//        递归终止条件是：path的长度为k
//        System.out.println(path);思路不清晰的话可以打印出每条路径path看下过程对理解很有帮助
        if (path.size() == k) {
            res.add(new ArrayList<Integer>(path));
            return res;
        }
//        遍历可能的搜索起点
        for (int i = start; i <= n; i++) {
//            向路径变量中添加一个数字
            path.add(i);
//            下一轮搜索，设置的搜索起点要加1，因为组合数里不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
//            重点理解这里，深度优化遍历有回头的过程，因此递归之前做了什么，递归之后就要做相同的逆操作
            path.remove(path.size() - 1);
        }
        return res;
    }
}

上面的题目是要求不能有重复元素的，下面给出一道可以有重复题目：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取

说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

一个简单的java解题代码如下：

这里假设target=7，candidate={2,3，6,7}

public class CombinationSum {
    public static void main(String[] args) {
        int target = 7;
        int[] candidates = {2, 3, 6, 7};
        CombinationSum shen = new CombinationSum();
        System.out.println("结果是：" + shen.combinationSum(candidates, target).toString());
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        判断cambinationSum是否为空，若是空值接返回不需要往下算了
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return null;
        }
//        创建路径记录变量
        List<Integer> path = new ArrayList<>();
        dfs(0,path,candidates,target,res);
        return res;
    }
    public void dfs(int start, List<Integer> path,  int[] candidates, int target,List<List<Integer>> res) {
//        根据终止条件这里先求出每个路径的和再来判断，容易理解，但是代码会比较臃肿
        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path.get(i);
        }
        System.out.println(path);//思路不清晰的话可以打印出每条路径path看下过程对理解很有帮助
//        下面的这两个if的判断条件非常重要，DFS里面需要思考的就是这个判断条件部分，其他部分的格式几乎是一样的
        if (sum > target) {
            return ;
        }
        if (sum == target) {
            res.add(new ArrayList<Integer>(path));
            return ;
        }
//       遍历可能的搜索起点
        for (int i = start; i < candidates.length; i++) {
//            想路径变量中添加元素
            path.add(candidates[i]);
//            这里需要注意一下第一个值：i， 元素可以重复的话搜索起点为：i;元素不可重复的话搜索起点为：i+1
            dfs( i, path, candidates, target, res);
//            深度优化搜索的回头过程，这里使用的是List作为搜索路径path，也可以使用其他容器
            path.remove(path.size()-1 );
        }
    }
}

上面两种做法只是完成了最基本的功能并没有进行优化，比较适合像我一样刚接触回溯和dfsd的小白，在这基础上可以进行剪枝，减去不合理路径，使得运算效率更快，下面是对借鉴的另一种解法：

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }
    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量，是 candidates 里的属性，可以不传
     * @param target     每减去一个元素，目标值变小
     * @param path       从根结点到叶子结点的路径，是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }
}

这是leetCode比较经典的解法，使用了剪枝，也用了Deque容器，进入链接看具体的讲解：

链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/