[数据结构与算法]力扣算法学习day19-3

力扣算法学习day19-3

39-组合总和

题目

代码实现

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        recall(0,target,candidates);
        
        return result;
    }
    public void recall(int i,int target,int[] candidates){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        
        for(int j = i;j < candidates.length && sum + candidates[j] <= target;j++){
            sum += candidates[j];
            path.add(candidates[j]);
            recall(j,target,candidates);
            sum -= candidates[j];
            path.remove(path.size()-1);
        }
        
    }
}

40-组合总和 II

题目

代码实现

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        recall(0,target,candidates);

        return result;
    }
    public void recall(int i,int target,int[] candidates){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int j = i;j < candidates.length && sum + candidates[j] <= target;j++){
            if(j > i && candidates[j] == candidates[j-1]){
                continue;
            }

            sum += candidates[j];
            path.add(candidates[j]);
            recall(j+1,target,candidates);
            sum -= candidates[j];
            path.remove(path.size()-1);
        }
    }
}