2024.4.20力扣每日一题——组合总和

2024.4.20

• • • 题目来源
    • 我的题解
    • • 方法一 回溯

题目来源

力扣每日一题；题序：39

我的题解

方法一 回溯

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        for(int i=0;i<candidates.length;i++){
            path.add(candidates[i]);
            dfs(candidates,target-candidates[i],i,path);
            path.remove(path.size()-1);
        }
        return res;

    }

    public void dfs(int[] candidates,int target,int index,List<Integer> path){
        if(target==0)
            res.add(new ArrayList<>(path));
        //后一个条件的前提是candidates数组是升序的，这里是看了官方的题解，感觉默认是有序的
        if(target<0||target-candidates[index]<0)
            return ;
        for(int next=index;next<candidates.length;next++){
            path.add(candidates[next]);
            dfs(candidates,target-candidates[next],next,path);
            path.remove(path.size()-1);
        }
    }
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~