参考课本装载问题Java实现子集和问题

子集和问题是一个经典的组合优化问题，给定一个包含 n 个正整数的集合 S，找出 S 的一些子集，使得这些子集的元素之和等于给定的目标数 t。

Java 实现子集和问题可以使用回溯算法，具体步骤如下：

1. 定义一个数组 nums，存储给定的 n 个正整数；
2. 定义一个布尔型数组 used，表示 nums 中的每个数是否已经被选中；
3. 定义一个函数 backtrack，它的参数包括：当前的选择列表（用一个列表 path 来存储），当前的选择路径的和 sum，以及目标数 t；
4. 在 backtrack 函数中，首先判断当前选择路径的和是否等于目标数 t，如果是，则将当前选择路径加入结果列表中；
5. 然后从 nums 数组中依次选择一个数，如果这个数没有被选过，则将它加入选择列表中，并将 used 对应位置设为 true，然后递归调用 backtrack 函数；
6. 递归结束后，回溯到上一层，将最后一个选择的数从选择列表中删除，并将 used 对应位置设为 false。

下面是 Java 代码实现：

import java.util.*;

public class SubsetSum {
    public static List<List<Integer>> subsetSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, 0, 0, target, new ArrayList<>(), res);
        return res;
    }

    private static void backtrack(int[] nums, boolean[] used, int start, int sum, int target, List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue; // 去重
            }
            if (!used[i] && sum + nums[i] <= target) {
                path.add(nums[i]);
                used[i] = true;
                backtrack(nums, used, i + 1, sum + nums[i], target, path, res);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int target = 5;
        List<List<Integer>> res = subsetSum(nums, target);
        for (List<Integer> path : res) {
            System.out.println(path);
        }
    }
}

运行结果为：

[1, 4]
[2, 3]
[5]