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.

Answer 2

This can be done by using a backtracking algorithm. This is equivalent to implementing a list of nested for loops. This can be better understood by trying to see the execution pattern of a sequence of nested for loops.

For example lets say you have, as you presented, a sequence of 3 fors and the code execution has reached the third level (the innermost). After this goes through all its iterations you return to the second level for where you go to the next iteration in which you jump again in third level for. Similarly, when the second level finishes all its iteration you jump back to the first level for which continues with the next iteration in which you jump in the second level and from there in the third.

So, in a given level you try go to the deeper one (if there is one) and if there are no more iterations you go back a level (back track).

Using the backtracking you represent the nested for by an array where each element is an index variable: array[0] is the index for for level 0, and so on.

Here is a sample implementation for your problem:

#define NUMBER_OF_OBJECTS  10
#define FORLOOP_DEPTH       4 // This is equivalent with the number of
                              // of nested fors and in the problem is
                              // the number of requested objects
#define FORLOOP_ARRAY_INIT -1 // This is a init value for each "forloop" variable
#define true  1
#define false 0
typedef int bool;
int main(void)
{
    int object_prices[NUMBER_OF_OBJECTS];
    int forLoopsArray[FORLOOP_DEPTH];
    bool isLoopVariableValueUsed[NUMBER_OF_OBJECTS];
    int forLoopLevel = 0;

    for (int i = 0; i < FORLOOP_DEPTH; i++)
    {
        forLoopsArray[i] = FORLOOP_ARRAY_INIT;
    }
    for (int i = 0; i < NUMBER_OF_OBJECTS; i++)
    {
        isLoopVariableValueUsed[i] = false;
    }


    forLoopLevel = 0; // Start from level zero
    while (forLoopLevel >= 0)
    {
        bool isOkVal = false;

        if (forLoopsArray[forLoopLevel] != FORLOOP_ARRAY_INIT)
        {
            // We'll mark the loopvariable value from the last iterration unused 
            // since we'll use a new one (in this iterration)
            isLoopVariableValueUsed[forLoopsArray[forLoopLevel]] = false;
        }

        /* All iterations (in all levels) start basically from zero
         * Because of that here I check that the loop variable for this level
         * is different than the previous ones or try the next value otherwise
        */
        while (    isOkVal == false
                && forLoopsArray[forLoopLevel] < (NUMBER_OF_OBJECTS - 1))
        {
            forLoopsArray[forLoopLevel]++; // Try a new value
            if (loopVariableValueUsed[forLoopsArray[forLoopLevel]] == false)
            {
                objectUsed[forLoopsArray[forLoopLevel]] = true;
                isOkVal = true;
            }
        }

        if (isOkVal == true) // Have we found in this level an different item?
        {
            if (forLoopLevel == FORLOOP_DEPTH - 1) // Is it the innermost?
            {
                /* Here is the innermost level where you can test
                 * if the sum of all selected items is smaller than
                 * the target
                 */
            }
            else // Nope, go a level deeper
            {
                forLoopLevel++;
            }
        }
        else // We've run out of values in this level, go back
        {
            forLoopsArray[forLoopLevel] = FORLOOP_ARRAY_INIT;
            forLoopLevel--;
        }
    }
}