Recomended Combination Algorithms for Numbers with Ranges

Question

I am currently trying to write C# code that finds multiple arrays of integers that equal a specified total when they are summed up. I would like to find these combinations while each integer in the array is given a range it can be.

For example, if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 3 and 6, some possible combination are [1, 3, 6], [2, 2, 6], and [4, 2, 4].

What sort of algorithm would help with solving a problem like this that can run in them most efficient amount of time? Also, what other things should I keep in mind when transitioning this problem into C# code?

Answer 1

You cannot do much better than nested for loops/recursion. Though if you are familiar with the 3SUM problem you will know a little trick to reduce the time complexity of this sort of algorithm! If you have n ranges then you know what number you have to pick from the nth range after you make your first n-1 choices!

I will use an example to walk through my suggestion.

if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 5 and 6

First of all lets process the data to be a bit nicer to deal with. I personally like the idea of working with ranges that start at 0 instead of arbitrary numbers! So we subtract the lower bounds from the upper bounds:

(1 to 4) -> (0 to 3)
(2 to 4) -> (0 to 2)
(5 to 6) -> (0 to 1)

Of course now we need to adjust our target sum to reflect the new ranges. So we subtract our original lower bounds from our target sum as well!

TargetSum = 10-1-2-5 = 2

Now we can represent our ranges with just the upper bound since they share a lower bound! So a range array would look something like:

RangeArray = [3,2,1]

Lets sort this (it will become more obvious why later). So we have:

RangeArray = [1,2,3]

Great! Now onto the beef of the algorithm... the summing! For now I will use for loops as it is easier to use for example purposes. You will have to use recursion. Yeldar's code should give you a good starting place.

result = []
for i from 0 to RangeArray[0]:
    SumList = [i]
    newSum = TargetSum - i
    for j from 0 to RangeArray[1]:
        if (newSum-j)>=0 and (newSum-j)<=RangeArray[2] then
            finalList = SumList + [j, newSum-j]
            result.append(finalList)

Note the inner loop. This is what was inspired by the 3SUM algorithm. We take advantage of the fact that we know what value we have to pick from the third range (since it is defined by our first 2 choices).

From here you have to of course re-map the results back to the original ranges by adding the original lowerbounds to the values that came from the corresponding ranges.

Notice that we now understand why it may be a good idea to sort RangeList. The last range gets absorbed into the secondlast range's loop. We want the largest range to be the one that does not loop.

I hope this helps to get you started! If you need any help translating my pseudocode into c# just ask :)

Answer 2

I would do this using recursion. You can simply iterate over all possible values and see if they give a required sum.

Input

Let's suppose we have the following input pattern:

N S
min1 min2 min3 ... minN
max1 max2 max3 ... maxN

For your example

if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 3 and 6

it will be:

3 10
1 2 3
4 4 6

Solution

We have read our input values. Now, we just try to use each possible number for our solution.

We will have a List which will store the current path:

static List<int> current = new List<int>();

The recursive function is pretty simple:

private static void Do(int index, int currentSum)
{
    if (index == length) // Termination
    {
        if (currentSum == sum) // If result is a required sum - just output it
            Output();
        return;
    }

    // try all possible solutions for current index
    for (int i = minValues[index]; i <= maxValues[index]; i++) 
    {
        current.Add(i);
        Do(index + 1, currentSum + i); // pass new index and new sum
        current.RemoveAt(current.Count() - 1);
    }
}

For non-negative values we can also include such condition. This is the recursion improvement which will cut off a huge amount of incorrect iterations. If we already have a currentSum greater than sum then it is useless to continue in this recursion branch:

if (currentSum > sum) return;

Actually, this algorithm is a simple "find combinations that give a sum S" problem solution with one difference: inner loop indices within minValue[index] and maxValue[index].

Demo

Here is the working IDEOne demo of my solution.