Java 算法：求从 1 到 100 的所有组合和为 100 的方案

本文将介绍一种使用 Java 递归算法解决从 1 到 100 中，选取任意个数的数字组合，使其和为 100 的问题。

问题描述：

从 1 到 100 中，一个数、两个数、三个数或多个数一组，取任意组合，对组合里的数进行求和，求有多少组和为 100 的组合。

举例：

[100]
[1, 99]
[1, 2, 97]
[5, 6, 7, 8, 9, 11, 12, 13, 14, 15]

解题思路：

一种解法是使用递归，每次递归时，从当前数开始，依次加入下一个数，并计算组合的和，直到组合的和等于 100 或者当前数已经大于 100。在递归过程中，记录已经选择的数的个数，以及已经选择的数的和，当已经选择的数的和等于 100 时，统计一组符合要求的组合。

代码实现：

public class CombinationSum {
    public static void main(String[] args) {
        List<List<Integer>> result = combinationSum(1, 100);
        System.out.println("总共有" + result.size() + "组符合要求的组合：");
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }

    public static List<List<Integer>> combinationSum(int from, int to) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = from; i <= to; i++) {
            List<Integer> combination = new ArrayList<>();
            combination.add(i);
            combinationSum(result, combination, i, i, 1, to);
        }
        return result;
    }

    private static void combinationSum(List<List<Integer>> result, List<Integer> combination,
                                        int sum, int lastNum, int count, int to) {
        if (sum == 100) {
            result.add(new ArrayList<>(combination));
            return;
        }
        if (sum > 100 || lastNum > to) {
            return;
        }
        for (int i = lastNum + 1; i <= to; i++) {
            combination.add(i);
            combinationSum(result, combination, sum + i, i, count + 1, to);
            combination.remove(combination.size() - 1);
        }
    }
}

代码解释：

在主函数 main 中，我们调用 combinationSum(1, 100)，表示从 1 到 100 中所有的数都可以作为组合的第一个数。
combinationSum 方法递归计算符合要求的组合。
combinationSum 方法中的参数分别表示：
- result：保存符合要求的组合的列表。
- combination：保存当前的组合。
- sum：当前组合中已经选择的数的和。
- lastNum：当前组合中最后一个选择的数。
- count：当前组合中已经选择的数的个数。
- to：组合中可以选择的最大数。
在 combinationSum 方法开始时，我们先判断当前的组合是否符合要求，如果符合要求，就将其添加到 result 中，然后直接返回。
如果当前组合的和已经大于 100，或当前组合中最后一个选择的数已经大于 to，则直接返回。
否则，我们依次从 lastNum + 1 到 to 中选择下一个数，并将其加入到组合中，然后递归计算下一个数。递归结束后，我们需要将之前添加的数从组合中移除，以便进行下一次递归。

总结：

通过递归的方式，我们可以有效地找出从 1 到 100 中所有组合和为 100 的方案。本代码示例提供了一个清晰的实现，帮助你理解递归算法的应用。