Selecting items from a list to achieve a sum

Question

I have a list of items that has numeric values and I need to achieve a sum using these items. I need your help to build such an algorithm. Below, there is a sample that describes my problem, written in C#:

int sum = 21;

List<Item> list = new List<Item>();
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 5 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 12 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 2 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 7 });

List<Item> result = // the items in the list that has the defined sum.

Note: I have no constraint on the number of items in the result.

Answer 1

This is called the Subset sum problem and is considered a hard problem in computer science. Not hard as in hard to do, but hard to do fast — you can easily write an algorithm to do it, but for sizable inputs it will easily take billions of years.

If you are happy with a slow solution that is only practicable for small inputs, try something like this:

• Generate all subsets of the input list.

• For each subset, calculate the sum of the items in that subset.

• Return the first subset for which the sum matches.

Here is a method that returns all subsets (actually subsequences because it maintains the order of items, although in your case this makes no difference):

/// <summary>
/// Returns all subsequences of the input <see cref="IEnumerable&lt;T&gt;"/>.
/// </summary>
/// <param name="source">The sequence of items to generate
/// subsequences of.</param>
/// <returns>A collection containing all subsequences of the input
/// <see cref="IEnumerable&lt;T&gt;"/>.</returns>
public static IEnumerable<IEnumerable<T>> Subsequences<T>(
        this IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    // Ensure that the source IEnumerable is evaluated only once
    return subsequences(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> subsequences<T>(IEnumerable<T> source)
{
    if (source.Any())
    {
        foreach (var comb in subsequences(source.Skip(1)))
        {
            yield return comb;
            yield return source.Take(1).Concat(comb);
        }
    }
    else
    {
        yield return Enumerable.Empty<T>();
    }
}

So you can now write something like this...

var result = list.Subsequences()
                 .FirstOrDefault(ss => ss.Sum(item => item.Value) == sum);