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

I'm not exactly sure which sun you are after here. If you want the sum of all values combines, use this code:

int result = list.Sum( i => i.Value);

If you want all elements that has a specific value, use this code:

int x = 3;
List<Item> result = list.Where( i => i.Value == x);

Answer 2

recursive, add elements until A) you achieve the sum or B) you get too much, if A you're done, if B you change the elements trying all possible configurations. Maybe prohibit the system to add an element if the current element is already bigger than the last element that went over the sum

Answer 3

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);

Answer 4

That's called the subset sum problem, with the modification - that you don't want to get to zero, but to a specific number.

Here's what Wiki has to say about it - http://en.wikipedia.org/wiki/Subset_sum_problem.

You may think of some optimizations according to your knowledge of the domain. For example if the highest number + the lowest number are greater than the sum -> the highest number will never be used, and you can rule it out (and try the same for the new highest number..).

I remember doing it as Samuel suggested - the recursive way, which wasn't that terrible, (but of course there's always the stackoverflow issue...).