寻找商品价格组合：算法教程与代码示例

prices = [10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2]
amountOfMoney = 100

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

public class PriceCombinations {

    /**
     * 查找所有价格组合，使其总和等于目标金额。
     *
     * @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; // 默认允许重复组合

        // 检查是否提供了可选参数，以确定是否允许重复组合
        if (allowDuplicatesInList.length > 0) {
            allowDuplicates = allowDuplicatesInList[0];
        }

        // 递归地计算数组值的总和，并将总和等于目标值的组合添加到提供的列表中
        sumToTargetValue(list, new ArrayList<>(Arrays.stream(numbers).boxed().collect(
                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("]", ""));
            return;
        }
        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);
        }
    }
}

10, 3, 4, 80, 3
10, 3, 80, 7
10, 3, 80, 5, 2
10, 3, 80, 7
10, 80, 7, 3
10, 80, 5, 3, 2
10, 80, 3, 7
10, 90
15, 3, 80, 2
15, 80, 5
15, 80, 3, 2
3, 4, 90, 3
3, 80, 7, 5, 3, 2
3, 80, 7, 3, 7
3, 80, 5, 3, 7, 2
3, 90, 7
3, 90, 5, 2
3, 90, 7
3, 92, 5
3, 92, 3, 2
4, 80, 7, 7, 2
90, 7, 3
90, 5, 3, 2
90, 3, 7
92, 5, 3