当前位置: 首页 > article >正文

LeetCode:40. 组合总和 II(回溯 + 剪枝 Java)

目录

40. 组合总和 II

题目描述:

实现代码与解析:

回溯 + 剪枝

原理思路:


40. 组合总和 II

题目描述:

        给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[[1,1,6],[1,2,5],[1,7],[2,6]]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[[1,2,2],[5]]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

实现代码与解析:

回溯 + 剪枝

class Solution {


    private List<Integer> path = new ArrayList();
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        dfs(candidates, 0, target, 0);

        return res;
    }


    public void dfs(int[] candidates, int cur, int target, int idx) {

        if (cur == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (idx >= candidates.length) return;
        if (cur + candidates[idx] > target) return; // 如果大于,剪枝

        for (int i = idx; i < candidates.length; i++) {
            if (i > idx && candidates[i] == candidates[i - 1]) { // 同一位置不能重复选相同的数
                continue;
            }
            path.add(candidates[i]);
            dfs(candidates, cur + candidates[i], target, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
        return;
    }
}

原理思路:

        比较简单啊,看代码吧。回溯题。


http://www.kler.cn/a/525039.html

相关文章:

  • 白嫖DeepSeek:一分钟完成本地部署AI
  • 29. C语言 可变参数详解
  • SQL注入漏洞之高阶手法 宽字节注入以及编码解释 以及堆叠注入原理说明
  • 【Matlab高端绘图SCI绘图模板】第006期 对比绘柱状图 (只需替换数据)
  • 1.27补题 回训练营
  • LangChain的开发流程
  • Python3 【高阶函数】水平考试:30道精选试题和答案
  • SOME/IP--协议英文原文讲解4
  • 人工智能如何驱动SEO关键词优化策略的转型与效果提升
  • Unity阿里云OpenAPI 获取 Token的C#【记录】
  • Windows程序设计4:API函数URLDownloadToFile和ShellExecuteEx
  • Python3 【函数】:见证算法的优雅与力量
  • 论文阅读(十三):复杂表型关联的贝叶斯、基于系统的多层次分析:从解释到决策
  • 26.useScript
  • 如何将DeepSeek部署到本地电脑
  • Shell特殊状态变量以及常用内置变量总结
  • Kmesh v1.0 正式发布
  • 用JavaScript实现观察者模式
  • 小白爬虫冒险之反“反爬”:无限debugger、禁用开发者工具、干扰控制台...(持续更新)
  • 【16届蓝桥杯寒假刷题营】第2期DAY4
  • 安卓逆向之脱壳-认识一下动态加载 双亲委派(二)
  • 洛谷P3383 【模板】线性筛素数
  • 在Visual Studio Code自带的按键编译无法使用该怎么办
  • JavaScript_01
  • Baklib如何重新定义企业知识管理提升组织效率与创新力
  • MyBatis 缓存机制详解