我有一个项目，有数值的清单，我需要实现使用这些项目的总和。我需要你的帮助来建立这样一个算法。下面，有一个描述我的问题，用C＃编写的示例：

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.

推荐答案

这就是所谓的 子集和问题 ，被认为是计算机科学的一个难题。不难在很难做到，但很难做到的快速的 - 你可以很容易地编写一个算法来做到这一点，但对于相当大的投入，否则很容易采取的数十亿年

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