带有价格的数组或产品，如何找到给定金额的所有可能组合[已关闭]

Question

因此，我得到了一系列产品的价格以及我拥有且可以花费的固定金额。问题是返回我可以用我拥有的固定金额购买的所有给定产品组合的列表。 例如。价格 = [10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2.....]（允许重复，因为它们代表不同的产品） 金额 = 100 结果 = {[90, 10], [90, 5, 3, 2], [90, 5, 3, 2], [....]}

我的想法是：

1. 对数组进行排序
2. 两个嵌套循环，以便将外部循环作为第一个产品，然后将其相加 ... 并没有真正按照我的想法进行......

有什么想法吗？有什么帮助吗？

Answer 1

下面是示例代码，演示了如何实现这一点（不进行排序）。为了完成此特定任务，该方法被命名为 combinationsEqualTarget()，并且它与一个名为 sumToTargetValue() 进行求和的递归辅助方法一起使用。请务必阅读代码中的注释：

/**
 * This method will take your supplied int[] array and the supplied target
 * value and fill your supplied String List with all the combinations
 * of elements within the int[] array that will equal the supplied target
 * value.
 * <p>
 * <b>Example Usage:</b><pre>
 * {@code
 *         List<String> myList = new ArrayList<>();
 *          int myTarget = 53;
 *          int[] a = {1, 2, 5, 10, 10, 25, 25, 25, 50};
 *          CombinationsEqual(myList, a, myTarget, false);
 *          for (String strg : myList) {
 *              System.out.println(strg);
 *          }
 * }
 * Console output will be:  1, 2, 5, 10, 10, 25
 *                          1, 2, 25, 25
 *                          1, 2, 50</pre><br>
 *
 * @param array           (String List Interface) A List Interface variable 
 *                        you declare and pass to this method. The method 
 *                        will fill your ArrayList with the appropriate
 *                        combinations that meet target.<br>
 *
 * @param numbers         (int[] Array) The int[] array to supply which
 *                        contains all the different values which can equal
 *                        the supplied target value when elemental values
 *                        are summed.<br>
 *
 * @param target          (int) The target value to get combinations
 *                        for.<br>
 *
 * @param allowDuplicatesInList (Optional - boolean - Default is 'true') Allow for
 *                              or disallow for duplicate combinations within your
 *                              list.
 */
public static void combinationsEqualTarget(List<String> list, int[] numbers, 
                               int target, boolean... allowDuplicatesInList) {
    boolean allowDuplicates = true; //Default - We do allow duplicate List elements.
    
    /* Has somethig been supplied to our optional allowDuplicates (varArgs) 
       parameter? If so then update the allowDuplicates boolean variable.*/
    if (allowDuplicatesInList.length > 0) {
        allowDuplicates = allowDuplicatesInList[0];
    }

    /* Recursively sum up array values and add those combinations
       which equals our target value to the supplied List.  */
    sumToTargetValue(list, new ArrayList<>(Arrays.stream(numbers).boxed().collect(
                java.util.stream.Collectors.toList())), target, new ArrayList<>());

    /* Remove Duplicate elements from the List if asked to do
       so through the optional allowDuplicates parameter (if
       allowDuplicates has been supplied 'false').      */
    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--;
                }
            }
        }
    }
}


/**
 * This recursive method is used in conjunction with the combinationsEqualTarget() 
 * method and is not meant to be used alone.<br>
 * 
 * @param listToReturn ({@code List<String>})
 * 
 * @param numbers ({@code List<Integer>})
 * 
 * @param target (int)
 * 
 * @param temp ({@code List<Integer>})
 */
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);
    }
}

要使用 combinationsEqualTarget() 方法，您可以执行以下操作：

// The example int[] array you provided in your post:
int[] prices = {10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2};
int moneyToSpend = 100;  // Target value.

List<String> list = new ArrayList<>();  // List to hold results...
combinationsEqualTarget(list, prices, moneyToSpend);
    
// Display the list of results within the Console Window:
for (String items : list) {
    System.out.println(items);
}

使用示例 int[] 数组运行时，控制台窗口应显示：

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