当前位置：网站首页>39. 组合总和＆＆ 40. 组合总和2 ＆＆ 216. 组合总和3

39. 组合总和＆＆ 40. 组合总和2 ＆＆ 216. 组合总和3

2022-08-09 18:50:00 【糖葫芦零零七】

在这里插入图片描述

代码实现：

class Solution {
    
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public  List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex) {
    
       if(sum == target){
      // 找到目标集合
           res.add(new ArrayList<>(path));
           return;
       }

       for(int i = startIndex; i < candidates.length; i++){
    
           if(sum + candidates[i] > target){
      // 剪枝操作
               break;
           }

           sum += candidates[i];
           path.add(candidates[i]);
           backtracking(candidates, target, sum, i); // i 不进行 +1 操作，表示还可以从自身进行累加
           sum -= candidates[i];  // 回溯
           path.remove(path.size() -1 );  // 回溯
       }
    }
}

在这里插入图片描述

代码实现：

class Solution {
    
     List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        Arrays.sort(candidates);  // 排序
        backtracking(candidates, target, 0, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, int sum, int startIndex) {
    
        if(sum == target){
      // 终止条件
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex; i < candidates.length; i++){
    
            if(sum + candidates[i] > target){
    
                break;
            }
            
            if(i > startIndex && candidates[i] == candidates[i - 1]){
      // 去重部分，特别注意i > startIndex起始位置
                continue;
            }
            
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, sum, i+1);  // 这里的i要进行 +1 操作， 因为不能重复本身
            sum -= candidates[i];  // 回溯
            path.remove(path.size() - 1); // 回溯
        }
    }
}

在这里插入图片描述

代码实现：

class Solution {
    
   List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
    
        int[] nums = {
    1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtracking(nums, k, n, 0, 0);
        return res;
    }

    private void backtracking(int[] nums, int k, int n, int sum, int startIndex) {
    
        // 剪枝
        if(sum > n){
    
            return;
        }

        if(path.size() == k){
      // 终止条件
            if(sum == n){
    
                res.add(new ArrayList<>(path));
                return;  // 如果path.size() == k 但sum != targetSum 直接返回
            }
        }


        for(int i = startIndex; i < nums.length; i++){
    
            if(sum + nums[i] > n){
    
                break;
            }

            sum += nums[i];
            path.add(nums[i]);
            backtracking(nums, k , n , sum, i+1);  // 由于不可以重复，所以i要进行 + 1 操作
            sum -= nums[i];  // 回溯
            path.remove(path.size() - 1);  // 回溯
        }
    }
}