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

题目来源

力扣每日一题；题序：39

我的题解

方法一 回溯

以每一个位置开始深搜，直到target等于0或者小于0或者遍历完结束。
关键在于：注意去重 巧妙方法：传入一个index，是上一次遍历元素的位置，控制其不再去遍历前面的元素

时间复杂度：O($n\ast 2^n$)。n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候还会用 target−candidates[idx]≥0进行剪枝，所以实际运行情况是远远小于这个时间复杂度的。
空间复杂度：O(n)

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);
        }
    }
}

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