组合总和

力扣原题链接

问题描述

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

示例

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

解题思路

这是一个典型的回溯算法问题。我们需要在给定的数字数组中寻找所有可能的组合，使其和等于目标数 target。

代码思路

1. 初始化结果列表： 创建一个空的列表 result，用于存储最终的组合结果。
2. 回溯搜索： 定义一个回溯函数 backtrack，其参数包括当前处理的索引 start、当前的目标值 target、当前的组合路径 path。
3. 结束条件： 如果当前目标值等于 0，说明找到了一个有效组合，将其加入结果列表，并返回。
4. 选择列表： 候选数字数组中的所有数字。
5. 遍历选择： 从当前处理索引 start 开始遍历候选数字数组。
6. 做出选择： 将当前数字加入路径，并更新目标值为 target - candidates[i]。
7. 递归进入下一层： 递归调用回溯函数，传入新的索引 i 和更新后的目标值。
8. 撤销选择： 回溯到上一层时，将当前选择的数字从路径中删除。

Java解题

写法一

直接用target来减，return判断条件为target == 0

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) {
        // 结束条件：如果目标值为 0，说明找到了一个有效组合，将其加入结果列表
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 从当前处理索引开始遍历候选数字数组
        for (int i = start; i < candidates.length; i++) {
            // 做出选择：将当前数字加入路径，并更新目标值
            if (target - candidates[i] >= 0) {
                path.add(candidates[i]);
                // 递归进入下一层，传入新的索引和更新后的目标值
                backtrack(candidates, target - candidates[i], i, path, result);
                // 撤销选择：回溯到上一层时，将当前选择的数字从路径中删除
                path.remove(path.size() - 1);
            }
        }
    }
}

写法2

加入一个sum来收集当前path里的总和，return判断条件为sum = target

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        backstrack(candidates,target,0,0,path);
        return res;

    }
    public void backstrack(int[] candidates,int target,int index,int sum,List<Integer> path){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for( int i = index;i<candidates.length;i++){
            if(sum>target) return;
            if(candidates[i]>target) continue;
            path.add(candidates[i]);
            backstrack(candidates,target,i,sum+candidates[i],path);
            path.remove(path.size()-1);
        }
    }
}