leetcode-39. 组合总和

JAVA解法

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 求候选数组的长度
        int len = candidates.length;
        // 定义一个符合题目要求的返回值类型来储存结果集
        List<List<Integer>> res = new ArrayList<>();
        // 若传进来的选数组的长度为 0 则代表没数据，直接返回结果集
        if (len == 0) {
            return res;
        }

        // 对所有候选数排序
        Arrays.sort(candidates);
        // 定义一个队列来存放选中的候选数，也就是记录当前路径
        Deque<Integer> path = new ArrayDeque<>();
        // 进入深度优先搜索算法
        dfs(candidates, 0, len, target, path, res);
        // 返回最终结果集
        return res;
    }

    // 实现深度优先搜索算法
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 剪枝后进入递归主体
        for (int i = begin; i < len; i++) {
            // 由于候选数组已经有序，小于 0 的都剪掉
            if (target - candidates[i] < 0) {
                break;
            }
            // 这用来储存每一完整枝节上的所有数字，添加新的数字在枝节末，也就是本次循环所选择的数
            path.addLast(candidates[i]);
            // 进入递归
            dfs(candidates, i, len, target - candidates[i], path, res);
            // 删掉该续上的数，因为这个是这次循环的选择，下次循环也就是下个枝节是同个深度的但不是选这个数了
            path.removeLast();
        }
    }
}

题解分析

  这道题是回溯算法的典型应用，在回溯算法的基础上加上了剪枝优化算法。首先，我们求候选数组的长度，再定义一个符合题目的返回结果集类型的变量用于存放结果集，若传进来的选数组的长度为 0 则代表没数据，直接返回空结果集即可。对所有候选数排序，定义一个队列来记录当前路径，就是一棵树的某分支的路径。
  dfs 的实现重点是路径记录和剪枝，侯选数与 target 作差小于 0 的停止循环，大大节省了时间和空间，而路径的记录则记得每次要出队最后一个，因为下个路径是同深度的不同树节点，最终遍历完后就返回结果集即可。

leetcode原题：39. 组合总和