在列表中查找加起来等于目标数的元素

List<int> _arr = new List<int> {1, 3, 4};

一旦我们有了获取枚举器/列表的所有子集的方法，这就很容易了
(在这里找到:答案:在c#中获得数组所有子集的最优雅的方法)

using System;
using System.Collections.Generic;
using System.Linq;
public static class Program
{
    static void Main(string[] args)
    {
        var test = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        var target = 6;
        var matches = from subset in test.SubSetsOf()
                      where subset.Sum() == target
                      select subset;
        Console.WriteLine("Numbers: {0}", test.Select(i => i.ToString()).Aggregate((a, n) => a + ", " + n));
        Console.WriteLine("Target: {0}", target);
        foreach (var match in matches)
        {
            Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => a + " + " + n) + " = " + target.ToString());
        }
        Console.ReadKey();
    }
    public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(this IEnumerable<T> source)
    {
        // Deal with the case of an empty source (simply return an enumerable containing a single, empty enumerable)
        if (!source.Any())
            return Enumerable.Repeat(Enumerable.Empty<T>(), 1);
        // Grab the first element off of the list
        var element = source.Take(1);
        // Recurse, to get all subsets of the source, ignoring the first item
        var haveNots = SubSetsOf(source.Skip(1));
        // Get all those subsets and add the element we removed to them
        var haves = haveNots.Select(set => element.Concat(set));
        // Finally combine the subsets that didn't include the first item, with those that did.
        return haves.Concat(haveNots);
    }
}

输出:

Numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9
Target: 6
1 + 2 + 3 = 6
1 + 5 = 6
2 + 4 = 6
6 = 6

我认为解决这个问题的最好方法是动态规划。

创建一个维度为[a + 1， _arr]的二维数组。长度:

  0 1 2 3 4
1
3
4

然后，对于该2D数组中的每一列，填充每个单元格，使列中所有单元格的总和等于该列的索引:

  0 1 2 3 4
1 0 1 x 0 1
3 0 0 x 1 1
4 0 0 x 0 0
// Alternative solution
  0 1 2 3 4
1 0 1 x 0 0
3 0 0 x 1 0
4 0 0 x 0 1

这里，x表示无解。此外，第4列有两个解决方案，因此您需要考虑到这一点，可能需要使用List<int>[a] ?

关于如何准确地填充单元格:
列0将保留所有零，因为它是一个不需要求和的解决方案。
对于列i，您希望执行i - n(其中n是来自_arr的当前数字)

  0 1
1 0 1   // 1 - 1 == 0, so you put 1 in here
3 0 0
4 0 0
  0 1 2
1 0 1 x // 2 - 1 == 1, 1 already has a solution, but you already used the number necessary to solve 1
3 0 0 x
4 0 0 x

如果您有多个1 s

  0 1 2
1 0 1 1 //             1 - 1 == 0
1 0 0 1 // 2 - 1 == 1, 1 already has a solution
3 0 0 0
4 0 0 0
// Alternative solution
  0 1 2
1 0 0 1 // 2 - 1 == 1, 1 already has a solution
1 0 1 1 //             1 - 1 == 0
3 0 0 0
4 0 0 0

如果你需要更多关于动态规划的信息:背包问题动态规划算法

我不认为你可以使用一个简单的LINQ查询。事实上，我很难想出一个使用成熟的T-SQL的简单解决方案!

问题是您试图返回的不是单个项目，而是基于可能的排列的各种项目集合。

在这一点上，我确实希望有人能提出这样一个LINQ查询，因为有些东西告诉我这将是非常棒的。div;)