Given an array, find combinations of n numbers that are less than c

Question

This is a tough one, at least for my minimal c skills.

Basically, the user enters a list of prices into an array, and then the desired number of items he wants to purchase, and finally a maximum cost not to exceed.

I need to check how many combinations of the desired number of items are less than or equal to the cost given.

If the problem was a fixed number of items in the combination, say 3, it would be much easier with just three loops selecting each price and adding them to test.

Where I get stumped is the requirement that the user enter any number of items, up to the number of items in the array.

This is what I decided on at first, before realizing that the user could specify combinations of any number, not just three. It was created with help from a similar topic on here, but again it only works if the user specifies he wants 3 items per combination. Otherwise it doesn't work.

// test if any combinations of items can be made
  for (one = 0; one < (count-2); one++) // count -2 to account for the two other variables
  {
    for (two = one + 1; two < (count-1); two++) // count -1 to account for the last variable
    {
      for (three = two + 1; three < count; three++)
      {
        total = itemCosts[one] + itemCosts[two] + itemCosts[three];
        if (total <= funds)
        {
          // DEBUG printf("\nMatch found! %d + %d + %d, total: %d.", itemCosts[one], itemCosts[two], itemCosts[three], total);
          combos++;
        }
      }
    }
  }

As far as I can tell there's no easy way to adapt this to be flexible based on the user's desired number of items per combination.

I would really appreciate any help given.

Answer 1

One trick to flattening nested iterations is to use recursion.

Make a function that takes an array of items that you have selected so far, and the number of items you've picked up to this point. The algorithm should go like this:

• If you have picked the number of items equal to your target of N, compute the sum and check it against the limit
• If you have not picked enough items, add one more item to your list, and make a recursive call.

To ensure that you do not pick the same item twice, pass the smallest index from which the function may pick. The declaration of the function may look like this:

int count_combinations(
    int itemCosts[]
,   size_t costCount
,   int pickedItems[]
,   size_t pickedCount
,   size_t pickedTargetCount
,   size_t minIndex
,   int funds
) {
    if (pickedCount == pickedTargetCount) {
        // This is the base case. It has the code similar to
        // the "if" statement from your code, but the number of items
        // is not fixed.
        int sum = 0;
        for (size_t i = 0 ; i != pickedCount ; i++) {
            sum += pickedItems[i];
        }
        // The following line will return 0 or 1,
        // depending on the result of the comparison.
        return sum <= funds;
    } else {
        // This is the recursive case. It is similar to one of your "for"
        // loops, but instead of setting "one", "two", or "three"
        // it sets pickedItems[0], pickedItems[1], etc.
        int res = 0;
        for (size_t i = minIndex ; i != costCount ; i++) {
            pickedItems[pickedCount] = itemCosts[i];
            res += count_combinations(
                itemCosts
            ,   costCount
            ,   pickedItems
            ,   pickedCount+1
            ,   pickedTargetCount
            ,   i+1
            ,   funds
            );
        }
        return res;
    }
}

You call this function like this:

int itemCosts[C] = {...}; // The costs
int pickedItems[N]; // No need to initialize this array
int res = count_combinations(itemCosts, C, pickedItems, 0, N, 0, funds);

Demo.