039.组合总和

鲁迅没说过：今天是周六，但不影响我继续刷一道二哥的 LeetCode 刷题笔记。遇到组合这种题，无非就是遍历、递归、回溯，多练习几次就能掌握了。

题意

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

candidates 中的 同一个 数字可以 无限制 重复 被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

难度

中等

示例

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

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

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

分析 1

说实话，这道题目描述了很多，都不如看一个示例，一看就懂。

从示例中可以看得出来，这道题需要我们从整数数组中不断地排列组合，找出所有符合要求的答案。

并且可以重复使用数组中的元素。和之前的两数之和，三数之和有类似的地方。

最容易想到的办法就是一个个枚举，然后判断是否符合条件，如果符合条件就加入到答案中。

class Solution03901 {
    // 主方法，找到所有组合，使得组合中数字的和为目标值 target
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 初始化结果列表，用于存储所有符合条件的组合
        List<List<Integer>> result = new ArrayList<>();
        // 调用辅助方法，生成所有可能的组合
        generateAllCombinations(candidates, target, new ArrayList<>(), result, 0);
        // 返回结果列表
        return result;
    }

    // 辅助方法，递归生成所有可能的组合
    private void generateAllCombinations(int[] candidates, int target, List<Integer> combination, List<List<Integer>> result, int start) {
        // 计算当前组合的和
        int sum = combination.stream().mapToInt(Integer::intValue).sum();
        // 如果当前组合的和大于目标值，返回（剪枝）
        if (sum > target) {
            return;
        }