组合总和-Leetcode

简介: 组合总和-Leetcode

每日题目

题目:组合总和


给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。


candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。


对于给定的输入,保证和为 target 的不同组合数少于 150 个。


示例:


示例 1:


输入:candidates = [2,3,6,7], target = 7

输出:[[2,2,3],[7]]

解释:

2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。

7 也是一个候选, 7 = 7 。

仅有这两种组合。


示例 2:


输入: candidates = [2,3,5], target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]


示例 3:


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

输出: []


提示:


1 <= candidates.length <= 30

1 <= candidates[i] <= 200

candidate 中的每个元素都 互不相同

1 <= target <= 500


代码:


class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res =  new ArrayList<>();
        //如果数组为空,直接返回空结果
        if(candidates==null||candidates.length==0){
            return res;
        }
        //先排序
        Arrays.sort(candidates);
        //dfs
        dfs(candidates,target,0,new ArrayList<>(),res);
        return res;
    }
    public void dfs(int[] candidates,int target ,int start,List<Integer> list,List<List<Integer>> res){
        //如果目标值为0,说明已经找到一个组合,添加到结果集中
        if(target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        //遍历数组
        for (int i = start; i < candidates.length; i++) {
            //如果当前值大于目标值,则不需要继续遍历
            if(candidates[i]>target){
                return;
            }
            list.add(candidates[i]);
            //更新目标值和起始位置
            dfs(candidates,target-candidates[i],i,list,res);
            //回溯,删除当前值
            list.remove(list.size()-1);
        }
    }
}

每日单词

1.png


以上就是组合总和-Leetcode的全部内容

相关文章
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1247 5
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1258 87
|
11天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1814 13
|
21天前
|
人工智能 运维 安全
|
4天前
|
资源调度
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
237 127
|
4天前
|
前端开发
Promise的then方法返回的新Promise对象有什么特点?
Promise的then方法返回的新Promise对象有什么特点?
184 2