leetcode39. 组合总和（java）

dfs bfs感觉也都不难 但还是不太会写 细节整不明白呜呜呜

感谢lc官解

class Solution {
    public List> combinationSum(int[] candidates, int target) {
        List> ans = new ArrayList<>();
        List list = new ArrayList<>();
        dfs(candidates, target, ans, list, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List> ans, List list, int flag){
        if(flag == candidates.length) return;
        if(target == 0){
            ans.add( new ArrayList(list));
            return;
        } 
        dfs(candidates, target, ans, list, flag + 1);
        if(target - candidates[flag] >= 0){
            list.add(candidates[flag]);
            dfs(candidates, target - candidates[flag], ans, list, flag);
            list.remove(list.size() - 1);
        }
    }
}