如何使用Java查找数组中元素组合以达到目标金额

碧海醫心

发布时间：2025-07-20 19:04:01

541人浏览过

来源于php中文网

原创

如何使用java查找数组中元素组合以达到目标金额

本文介绍了如何使用Java编程，在一个包含商品价格的数组中，找出所有可能的商品组合，使其总价等于给定的目标金额。文章提供了一个完整的Java代码示例，包括递归辅助函数，并详细解释了代码的实现逻辑和使用方法，帮助读者理解并应用该算法解决实际问题。

在实际编程中，我们经常会遇到需要从一组数据中找出满足特定条件的组合的问题。例如，给定一个包含商品价格的数组和一个目标金额，我们需要找出所有可能的商品组合，使得这些商品的总价等于目标金额。本文将介绍如何使用Java编程解决这类问题。

算法实现

解决这个问题的一种有效方法是使用递归。以下是一个Java代码示例，它展示了如何实现这个算法：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {

    /**
     * 查找数组中所有和为目标值的组合。允许重复数字。
     *
     * @param list  用于存储结果的列表
     * @param numbers 包含候选数字的数组
     * @param target 目标值
     * @param allowDuplicatesInList  是否允许结果列表中存在重复的组合
     */
    public static void combinationsEqualTarget(List list, int[] numbers,
                                               int target, boolean... allowDuplicatesInList) {
        boolean allowDuplicates = true; // 默认允许重复组合

        // 处理可选参数：是否允许重复组合
        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 listToReturn,
                                        List numbers, int target, List 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 remaining = new ArrayList<>();
            int n = numbers.get(i);
            for (int j = i + 1; j < numbers.size(); j++) {
                remaining.add(numbers.get(j));
            }
            List 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 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，一个包含候选数字的数组numbers，一个目标值target，以及一个可选的布尔参数allowDuplicatesInList，用于指定是否允许结果列表中存在重复的组合。

立即学习“Java免费学习笔记（深入）”；

ImgGood
免费在线AI照片编辑器

下载
sumToTargetValue(List listToReturn, List numbers, int target, List temp): 这是一个递归辅助函数，用于实际查找组合。它接收一个结果列表listToReturn，一个剩余的候选数字列表numbers，一个目标值target，以及一个当前组合temp。
- 该函数首先计算当前组合temp的和s。
- 如果s等于target，则将当前组合添加到结果列表listToReturn中。
- 如果s大于或等于target，则停止递归。
- 否则，该函数遍历剩余的候选数字列表numbers，对于每个数字n，创建一个新的组合tempRec，将n添加到tempRec中，并递归调用自身，传入剩余的候选数字列表和新的组合。