本文介绍如何使用Java编程，在一个给定的整数数组中，找出所有元素组合，使其总和等于一个特定的目标值。文章提供了一个递归解决方案，并附带详细的代码示例和解释，帮助读者理解和应用该算法。
问题描述
给定一个整数数组 prices 和一个目标值 amountOfMoney，目标是找到 prices 中所有元素组合，使得这些元素的总和等于 amountOfMoney。数组中允许存在重复元素，因为它们代表不同的产品。例如：
prices = [10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2] amountOfMoney = 100
期望的结果是一个包含所有符合条件的组合的列表，例如 [[90, 10], [90, 5, 3, 2], …]。
解决方案
以下Java代码展示了如何实现该功能。该方案使用了递归方法 sumToTargetValue() 来查找所有可能的组合。
立即学习“Java免费学习笔记（深入）”；
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CombinationSum { /** * 查找数组中所有元素组合，使其总和等于目标值。 * * @param list 存储结果的列表 * @param numbers 输入的整数数组 * @param target 目标值 * @param allowDuplicatesInList 是否允许结果列表中存在重复组合（可选，默认为 true） */ public static void combinationsEqualTarget(List<String> list, int[] numbers, int target, Boolean... allowDuplicatesInList) { boolean allowDuplicates = true; // 默认允许重复组合 // 检查是否提供了可选参数 allowDuplicatesInList if (allowDuplicatesInList.length > 0) { allowDuplicates = allowDuplicatesInList[0]; } // 递归地计算数组值的总和，并将等于目标值的组合添加到列表中 sumToTargetValue(list, new ArrayList<>(Arrays.stream(numbers).boxed().collect( java.util.stream.Collectors.toList())), target, new ArrayList<>()); // 如果不允许重复组合，则从列表中删除重复项 if (!allowDuplicates) { for (int i = 0; i < list.size(); i++) { for (int j = i + 1; j < list.size(); j++) { if (list.get(i).equals(list.get(j))) { list.remove(j); j--; } } } } } /** * 递归方法，用于计算数组值的总和。 * * @param listToReturn 存储结果的列表 * @param numbers 剩余的数字列表 * @param target 目标值 * @param temp 当前组合的临时列表 */ private static void sumToTargetValue(List<String> listToReturn, List<Integer> numbers, int target, List<Integer> temp) { int s = 0; for (int x : temp) { s += x; } if (s == target) { listToReturn.add(temp.toString().replace("[", "").replace("]", "")); } if (s >= target) { return; } for (int i = 0; i < numbers.size(); i++) { List<Integer> remaining = new ArrayList<>(); int n = numbers.get(i); for (int j = i + 1; j < numbers.size(); j++) { remaining.add(numbers.get(j)); } List<Integer> tempRec = new ArrayList<>(temp); tempRec.add(n); sumToTargetValue(listToReturn, remaining, target, tempRec); } } public static void main(String[] args) { // 示例用法 int[] prices = {10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2}; int moneyToSpend = 100; // 目标值 List<String> list = new ArrayList<>(); // 用于存储结果的列表 combinationsEqualTarget(list, prices, moneyToSpend); // 在控制台窗口中显示结果列表 for (String items : list) { System.out.println(items); } } }
代码解释
-
combinationsEqualTarget(List
list, int[] numbers, int target, boolean… allowDuplicatesInList) :- 此方法接收一个 List 用于存储结果，一个 int[] 数组作为输入，一个 int 目标值，以及一个可选的 boolean 参数，用于指定是否允许在列表中包含重复的组合。
- 它首先创建一个 ArrayList，将输入数组转换为列表。
- 然后，它调用递归方法 sumToTargetValue() 来查找所有可能的组合。
- 最后，如果 allowDuplicates 为 false，它将从列表中删除所有重复的组合。
-
sumToTargetValue(List
listToReturn, List :numbers, int target, List temp) - 这是一个递归方法，用于查找所有可能的组合。
- listToReturn：存储结果的列表。
- numbers：剩余的数字列表。
- target：目标值。
- temp：当前组合的临时列表。
- 该方法首先计算 temp 列表中所有元素的总和。
- 如果总和等于目标值，则将 temp 列表转换为字符串并添加到 listToReturn 中。
- 如果总和大于或等于目标值，则返回。
- 否则，它遍历 numbers 列表中的每个元素。
- 对于每个元素，它创建一个新的 remaining 列表，其中包含 numbers 列表中剩余的元素。
- 然后，它创建一个新的 tempRec 列表，其中包含 temp 列表中的所有元素以及当前元素。
- 最后，它递归地调用 sumToTargetValue() 方法，并将 listToReturn、remaining、target 和 tempRec 作为参数传递。
使用示例
在 main 方法中，我们创建了一个 prices 数组和一个 moneyToSpend 变量，并调用 combinationsEqualTarget() 方法来查找所有可能的组合。 然后，我们将结果打印到控制台。
注意事项
总结
本文提供了一个使用Java查找数组中组合等于目标值的元素的解决方案。该方案使用了递归方法，并附带详细的代码示例和解释。读者可以根据自己的需求修改和优化该算法。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
