QUIZ: Calculate number of days combinations

Question

I would like to calculate the number of different types of days i can have that equal my set value.

For example, if someone has 30 days annual leave as part of there employment i would like to calculate what different sorts of holiday they could take.

An example would be:

5, 10, 5, 2, 2, 1, 5

As you can see the above will equal to 30.

The idea of the calculation is to give a prospective employee an idea of what sorts of days off they can take.

The returned values could also be:

10, 10, 10

This means that i need to calculate number combinations that equal to the total annual leave number.

The challenge can be completed in ANY programming langauge!

I have tried the following:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            // find all possible combinations of this list
            var input = new[] { "1", "2", "3", "4", "5", "6","7","8","9","10","11","12","13","14" };
            var output = FastPowerSet(input);

            Print(output);
            Console.ReadLine();
        }

        static T[][] FastPowerSet<T>(T[] seq)
        {
            var powerSet = new T[1 << seq.Length][];
            powerSet[0] = new T[0]; // starting only with empty set
            for (var i = 0; i < seq.Length; i++)
            {
                var cur = seq[i];
                var count = 1 << i; // doubling list each time
                for (var j = 0; j < count; j++)
                {
                    var source = powerSet[j];
                    var destination = powerSet[count + j] = new T[source.Length + 1];
                    for (var q = 0; q < source.Length; q++)
                        destination[q] = source[q];
                    destination[source.Length] = cur;
                }
            }
            return powerSet;
        }

        static void Print<T>(T[][] seq)
        {
            for (var i = 0; i < seq.Length; i++)
            {
                var line = new StringBuilder();
                for (var j = 0; j < seq[i].Length; j++)
                {
                    line.AppendFormat("{0}, ", seq[i][j]);
                }
                Console.WriteLine(line);
            }
        }
    }
}

@NinaScholz: 10,10,10 tells us that the person can have 3 10 day holidays. — PriceCheaperton, Aug 01 '16 at 12:51
[Here you go](http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum), an extensive answer to your problem. Basically, you can use Dynamic Programming to do this, [as shown here](http://stackoverflow.com/a/18308020/1595197) — Sander, Aug 01 '16 at 13:03

score 1 · Accepted Answer · edited May 23 '17 at 12:33

Thank you PriceCheaperton!

A somewhat wider question have been answered here where restrictions of the sizes of the parts of the given sum can be given as well.

In the Python solution on top of the link above you would modify the call to the function like this to solve your particular example (I don't know if 15..30 is valid, otherwise you need to complete the list the same way I've started it):

subset_sum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15..30],30)

Best Regards, Mats

QUIZ: Calculate number of days combinations

1 Answers1