【刷题1】LeetCode 39. 组合总和 java基础

题目

https://leetcode-cn.com/problems/combination-sum/

分析

我们可以选择当前数或跳过当前数。
这题数字可以被重复使用。

代码

class Solution {
    List<List<Integer>> res;
    int[] candidates;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates=candidates;
        res=new ArrayList<List<Integer>>();
        dfs(new ArrayList<Integer>(),0,target);
        return res;
    }
    public void dfs(ArrayList<Integer> tmp,int index,int target){
        if(index>candidates.length-1){
            return;
        }
        if(target==0){
           res.add(new ArrayList(tmp));
           return;
        }
        //直接跳过，不选取当前数
        dfs(tmp,index+1,target);   
        //选择当前数     
        if(target>=candidates[index]){
            tmp.add(candidates[index]);
            dfs(tmp,index,target-candidates[index]);
            //恢复
            tmp.remove(tmp.size()-1);
            return;
        }
    } 
}

复杂度

结果