day-20 组合总和

参考了答案。。。。。。

思路：利用dfs对所有可能进行尝试，用id作为当前位置的索引，当idcandidates.length失败当target0时，添加当前组合，直至遍历完毕

注意：res.add(new ArrayList(now)) 不能为res.add(now)),否则为空

code:

class Solution {

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

        List<List<Integer>> res=new ArrayList<List<Integer>>();
        List<Integer> now=new ArrayList<Integer>();
        dfs(res,now,candidates,target,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> now,
    int[] candidates, int target,int id){

        if(id==candidates.length) return;
        if(target==0){

            res.add(new ArrayList<Integer>(now));
            return;
        }
        dfs(res,now,candidates,target,id+1);
        if(target-candidates[id]>=0){

            now.add(candidates[id]);
            dfs(res,now,candidates,target-candidates[id],id);
            now.remove(now.size()-1);
        }
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136749305

目录