Splitting a number over several ranges

Question

I am trying to split a number into smaller numbers that fit predefined ranges and I can't seem to get the algorithm right. I am using C#.

Example

Split 20 into three numbers where the numbers have to fit the following ranges: 1-3, 3-10, and 0-15. Final numbers could look like this: 1,5,14 or 2,3,15

Another example could be to split 100 into four numbers that fit the following ranges: 0-10, 0-10, 0-40, 0-40. The result would naturally be 10,10,40,40. Splitting 90 on the same ranges could result 5,8,38,39 etc.

Can you kick me in the right direction?

(no, it's not a homework, it's for a personal project)

Answer 1

You can do it using recursion.

The idea of the algorithm is something like this:

• In every execution you're going to iterate through all possible numbers of the interval.

• Calls recursive to generate the next number of the next interval.

• If at any time the sum passes the desired value then backtracks.

• Once all the numbers are generated, if the sum is equal to the desired number then you have a possible combination.

It can be improved but it is a solution.

The following code prints all valid sequences in the console:

SplitNumber(100, new Interval[]
{
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 40 },
    new Interval { Min = 0, Max = 40 },
});

public static void SplitNumber(int n, Interval[] intervals)
{
    SplitNumber(n, 0, intervals, "");
}

public static void SplitNumber(int n, int k, Interval[] intervals, string s)
{
    if (n < 0) return;

    if (k >= intervals.Length) { if (n == 0) Console.WriteLine(s); }
    else
        for (int i = intervals[k].Min; i <= intervals[k].Max; i++)
            SplitNumber(n - i, k + 1, intervals, string.Format("{0} {1}", s, i));
}

Interval class is something like this:

public class Interval
{
    public int Min { get; set; }
    public int Max { get; set; }
}