首页 > 其他分享 >【Hot100】LeetCode—39. 组合总和

【Hot100】LeetCode—39. 组合总和

时间:2024-08-28 09:55:14浏览次数:15  
标签:39 target nowSum int new candidates path Hot100 LeetCode

目录



1- 思路

注意如果借助 startIndex 实现,理解 startIndex 的含义

  • 在本题目中,由于同一个元素可以重复选取,因此 startIndex 在传递的过程中,不需要进行 +1 操作,传递的值为i

2- 实现

⭐39. 组合总和——题解思路

在这里插入图片描述

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracing(candidates, target, 0, 0);
        return res;
    }

    // 1. 回溯参数及返回值
    public void backTracing(int[] candidates, int target, int nowSum, int startIndex) {

        if (nowSum > target) {
            return;
        }

        // 2. 结束条件
        if (nowSum == target) {
            res.add(new ArrayList(path));
            return;
        }

        // 回溯
        for (int i = startIndex; i < candidates.length; i++) {
            nowSum += candidates[i];
            path.add(candidates[i]);
            backTracing(candidates, target, nowSum, i);
            nowSum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

3- ACM 实现

public class combination {


    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static List<List<Integer>> combine(int[] candidates,int target){
        // 回溯
        backTracing(candidates,target,0,0);
        return res;
    }

    public static void backTracing(int[] candidates,int target,int nowSum,int startIndex){

        // 终止条件
        if(nowSum>target){
            return;
        }
        if(nowSum==target){
            res.add(new ArrayList<>(path));
        }

        //回溯
        for(int i = startIndex;i<candidates.length;i++){
            nowSum += candidates[i];
            path.add(candidates[i]);
            backTracing(candidates,target,nowSum,i);
            nowSum -= candidates[i];
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.replace("[","").replace("]","");
        String[] parts = input.split(",");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < parts.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        System.out.println("输入target");
        int target = sc.nextInt();
        System.out.println("结果是"+combine(nums,target).toString());

    }
}

标签:39,target,nowSum,int,new,candidates,path,Hot100,LeetCode
From: https://blog.csdn.net/weixin_44382896/article/details/141632862

相关文章

  • 【Hot100】LeetCode—17. 电话号码的字母组合
    目录1-思路String数组(哈希表)+回溯2-实现⭐17.电话号码的字母组合——题解思路3-ACM实现题目连接:17.电话号码的字母组合1-思路String数组(哈希表)+回溯思路通过String数组实现哈希表,存储0-9的哈希表映射回溯三部曲①参数及返回值numToStr:Stri......
  • Dijkstra's algorithm All In One
    Dijkstra'salgorithmAllInOne迪杰斯特拉算法DijkstraDijkstra'salgorithm(/ˈdaɪkstrəz/DYKE-strəz)isanalgorithmforfindingtheshortestpathsbetweennodesinaweightedgraph,whichmayrepresent,forexample,roadnetworks.Dijkstra算法是一种......
  • 【Leetcode_Hot100】普通数组
    普通数组53.最大子数组和56.合并区间189.轮转数组238.除自身以外数组的乘积41.缺失的第一个正数53.最大子数组和方法一:暴力解依次遍历数组中的每个子数组,进而判断res的最大值超时classSolution{publicintmaxSubArray(int[]nums){intres=0;......
  • 135. 分发糖果(leetcode)
    https://leetcode.cn/problems/candy/description/贪心,策略是确定一侧的正确性,再确定另一侧的正确性,最后综合作为正确答案,其中先确定一侧的正确性是局部最优,确定两侧的正确性的局部最优,且找不到反例就可以推出全局最优答案classSolution{publicintcandy(int[]ra......
  • MySQL 2003 - Can’t connect to MySQL server on ' '(10060)
    2003-Can’tconnecttoMySQLserveron''(10060) 一般是以下几个原因造成的:1.网络不通畅2.mysql服务未启动3.防火墙未开放端口4##云服务器的安全组规则未设置  一般是以下几个原因造成的:1.网络不通畅:【mysql-u-p,看看能不能登陆】2.mysql服务未启动:......
  • esp-idf vscode debug command 'espIdf.getXtensaGdb' not found
    esp32idfvscodedebug错误vscode中配置文件采用的是正点原子的,调用gdb的时候,提示报错,找不到相应的命令launch.json文件中gdb的配置如下{"version":"0.2.0","configurations":[ { "name":"GDB", "type":"cppdbg", &......
  • mysql8.0.39采用克隆方式快速搭建主从同步
    mysql8.0.39采用克隆方式快速搭建主从同步备注:基于物理文件拷贝,数据量越大,越能体现出这种优势。8.0.17以上都可以使用 一、环境192.168.0.101主库192.168.0.102从库Serverversion:8.0.39 二、查看是否已经安装克隆插件#如果没有同步账号,可以新建一个dropus......
  • SQL基础综合练习题(39题)
    https://download.csdn.net/download/ruyigongfang/89681313可以用这个文件的建表语句在自己的pysql执行,就有该练习用的表。https://download.csdn.net/download/ruyigongfang/89681312该链接是只有题没有答案的文档。所用到的表:student(学生表):sno(学号),sname(学生姓名),ssex(学......
  • flutter使用flutter_datetime_picker时导入冲突 'DatePickerTheme' is imported from
    安装flutter_datetime_picker后运行项目出现下面的报错 在ChipsInput小部件中,您使用了两个相互冲突的导入。在调用this.theme=theme??DatePickerTheme()时会发生冲突,因为它不知道使用哪个导入,因为它们具有相同的名称。您需要删除import'package:flutter/src/material/date......
  • 从Flow小白到专家,Winter '25让流程自动化更简单!
    Salesforce平台每月提供超过1万亿次自动化服务,每月可节省超1090亿小时,预计为客户创造超2万亿美元的商业价值。这是一组不可思议的数字,充分展现了软件自动化的力量。Flow是整个Salesforce平台自动化的未来,一直在将大量资源用于开发Flow创新。本次Winter'25中自然也少不了Flow的......