侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-39. 组合总和

阿里灰太狼
2022-04-28 / 0 评论 / 0 点赞 / 220 阅读 / 1,237 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

39. 组合总和0
39. 组合总和1

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. 组合总和

0

评论区