So I am given an array of prices of products and a fixed amount of money I have and can spend. The question is to return a list of all given combinations of products that I can buy with the fixed amount of money I have. eg. prices = [10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2.....] (duplicates are allowed cause they represent different products) amountOfMoney = 100 result = {[90, 10], [90, 5, 3, 2], [90, 5, 3, 2], [....]}

My thought was:

1. Sort the array
2. two nested loops, in order to have the outside loop as the first product and then add up to that one ... doesn't really work out the way I thought it...

Any ideas? Any help?

CodePudding user response：

Below is example code which demonstrates how this can be accomplished (no sorting is carried out). For the sake of this particular task, the method is named combinationsEqualTarget() and it works with a recursive helper method that does the summing named sumToTargetValue(). Be sure to read the comments in code:

/**
 * 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);
    }
}

To use the combinationsEqualTarget() method, you might do something like this:

// 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);
}

When run with the example int[] Array, the Console Window should display:

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