leetcode-39. 组合总和

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();
        }
    }
}