How to efficiently generate all combinations (at all depths) whose sum is within a specified range

Question

Suppose you have a set of values (1,1,1,12,12,16) how would you generate all possible combinations (without repetition) whose sum is within a predefined range [min,max]. For example, here are all the combinations (of all depths) that have a range between 13 and 17:

1 12

1 1 12

1 1 1 12

16

1 16

This assumes that each item of the same value is indistinguishable, so you don't have three results of 1 12 in the final output. Brute force is possible, but in situations where the number of items is large, the number of combinations at all depths is astronomical. In the example above, there are (3 + 1) * (2 + 1) * (1 + 1) = 24 combinations at all depths. Thus, the total combinations is the product of the number of items of any given value + 1. Of course we can logically throw out huge number of combinations whose partial sum is greater than the max value (e.g. the set 16 12 is already bigger than the max value of 17, so skip any combinations that have a 16 and 12 in them).

I originally thought I could convert the input array into two arrays and increment them kind of like an odometer. But I am getting completely stuck on this recursive algorithm that breaks early. Any suggestions?

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

Edit

The integer values are just for demonstration. It can be any object that has a some sort of numerical value (int, double, float, etc...)

Typically there will only be a handful of unique values (~10 or so) but there can be several thousands total items.

Answer 1

An idea for another implementation:

Create from the list of numbers a list of stacks, each stack represents a number that appear in the list, and this number is pushed into the stack as many times as he appeared in the numbers list. more so, this list is sorted.

The idea is that you iterate through the stack list, in each stack you pop one number at a time if it doesn't exceed the max value and recall the function, and perform an additional call of skipping the current stack.

This algorithm reduces many redundant computations like trying to add different elements which have the same value when adding this value exceeds the maximal value.

I was able to solve pretty large problems with this algorithm (50 numbers and more), depending on the min and max values, obviously when the interval is very big the number of combinations may be huge.

Here's the code:

static void GenerateLimitedCombinations(List<int> intList, int minValue, int maxValue)
{
    intList.Sort();
    List<Stack<int>> StackList = new List<Stack<int>>();
    Stack<int> NewStack = new Stack<int>();
    NewStack.Push(intList[0]);
    StackList.Add(NewStack);

    for (int i = 1; i < intList.count; i++)
    {
        if (intList[i - 1] == intList[i])
            StackList[StackList.count - 1].Push(intList[i]);
        else
        {
            NewStack = new Stack<int>();
            NewStack.Push(intList[i]);
            StackList.Add(NewStack);
        }
    }

    GenerateLimitedCombinations(StackList, minValue, maxValue, 0, new List<int>(), 0);
}

static void GenerateLimitedCombinations(List<Stack<int>> stackList, int minValue, int maxValue, int currentStack, List<int> currentCombination, int currentSum)
{
    if (currentStack == stackList.count)
    {
        if (currentSum >= minValue)
        {
            foreach (int tempInt in CurrentCombination)
            {
                Console.Write(tempInt + " ");
            }
            Console.WriteLine(;
        }
    }

    else
    {
        int TempSum = currentSum;
        List<int> NewCombination = new List<int>(currentCombination);
        Stack<int> UndoStack = new Stack<int>();

        while (stackList[currentStack].Count != 0 && stackList[currentStack].Peek() + TempSum <= maxValue)
        {
            int AddedValue = stackList[currentStack].Pop();
            UndoStack.Push(AddedValue);
            NewCombination.Add(AddedValue);
            TempSum += AddedValue;
            GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, new List<int>(NewCombination), TempSum);
        }

        while (UndoStack.Count != 0)
        {
            stackList[currentStack].Push(UndoStack.Pop());
        }

        GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, currentCombination, currentSum);
    }
}

Here's a test program:

static void Main(string[] args)
{
    Random Rnd = new Random();
    List<int> IntList = new List<int>();
    int NumberOfInts = 10, MinValue = 19, MaxValue 21;

    for (int i = 0; i < NumberOfInts; i++) { IntList.Add(Rnd.Next(1, 10));
    for (int i = 0; i < NumberOfInts; i++) { Console.Write(IntList[i] + " "); } Console.WriteLine(); Console.WriteLine();

    GenerateLimitedCombinations(IntList, MinValue, MaxValue);
    Console.ReadKey();
}

Answer 2

The general tendency with this kind of problem is that there are relatively few values that will show up, but each value shows up many, many times. Therefore you first want to create a data structure that efficiently describes the combinations that will add up to the desired values, and only then figure out all of the combinations that do so. (If you know the term "dynamic programming", that's exactly the approach I'm describing.)

The obvious data structure in C# terms would be a Hashtable whose keys are the totals that the combination adds up to, and whose values are arrays listing the positions of the last elements that can be used in a combination that could add up to that particular total.

How do you build that data structure?

First you start with a Hashtable which contains the total 0 as a key, and an empty array as a value. Then for each element of your array you create a list of the new totals you can reach from the previous totals, and append your element's position to each one of their values (inserting a new one if needed). When you've gone through all of your elements, you have your data structure.

Now you can search that data structure just for the totals that are in the range you want. And for each such total, you can write a recursive program that will go through your data structure to produce the combinations. This step can indeed have a combinatorial explosion, but the nice thing is that EVERY combination produced is actually a combination in your final answer. So if this phase takes a long time, it is because you have a lot of final answers!

Answer 3

Switch the main call to:

GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);

and then add this code:

private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);

    for(int count = 0; count <= max_count; count++)
    {
        currentCombo[index] = count;
        if(index < currentCombo.Length - 1)
        {
            GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            int sum = Sum(currentCombo, values);
            if(sum >= min && sum <= max)
            {
                int[] copy = new int[currentCombo.Length];
                Array.Copy(currentCombo, copy, copy.Length);
                results.Add(copy);
            }
        }
    }
}

private static int Sum(int[] combo, int[] values)
{
    int sum = 0;
    for(int i = 0; i < combo.Length; i++)
    {
        sum += combo[i] * values[i];
    }
    return sum;
}

It returns the 5 valid answers.

Answer 4

This is quite similar to the subset sum problem which just happens to be NP-complete.

Wikipedia says the following about NP-complete problems:

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. This means that the time required to solve even moderately sized versions of many of these problems can easily reach into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

If indeed there is a way to solve this besides brute-forcing through the powerset and finding all subsets which sum up to a value within the given range, then I would be very interested in hearing it.

Answer 5

Try this algo

int arr[] = {1,1,1,12,12,16}
for(int i = 0;i<2^arr.Length;i++)
{
int[] arrBin = BinaryFormat(i); // binary format i
for(int j = 0;j<arrBin.Length;j++)
  if (arrBin[j] == 1)
     Console.Write("{0} ", arr[j]);
Console.WriteLine();
}