1

假设我有一个列表：

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

和一个目标4

我想使用给定列表中的 linq返回{1, 3}as1 + 3 = 4和{4}as 。4 = 4

我怎么做？

4

4 回答 4

10

一旦我们有一种方法来获取枚举器/列表的所有子集，这很容易
（在这里找到：答案：在 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
于 2013-05-17T09:02:52.147 回答
2

我认为这个问题的最佳解决方案是动态编程。

创建一个二维数组，维度为 [a + 1, _arr.Length]：

  0 1 2 3 4
1
3
4

然后，对于该二维数组中的每一列，填充每个单元格，使得一列的所有单元格的总和等于该列的索引：

  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 列有 2 个解决方案，因此您需要考虑这一点，也许使用List<int>[a]?

至于如何准确填写这些单元格：
列0将全为零，因为它是一种无需总和即可实现的解决方案。
对于 Column 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如果你有多个

  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

如果您需要有关动态规划的更多信息：背包问题动态规划算法

于 2013-05-17T09:13:22.273 回答
1

我认为您不能使用简单的 LINQ 查询来做到这一点。事实上，我很难想出一个使用成熟的 T-SQL 的简单解决方案！

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

在那张纸条上，我确实希望有人提出这样的 LINQ 查询，因为有些东西告诉我它会很棒。;)

于 2013-05-17T08:52:34.380 回答
1

如果您正在寻求一个非常好的和快速的解决方案来解决这个问题，那么您并不孤单。

这是一个众所周知的 SUBSET SUM 问题。我建议你可以在这里查看维基百科：

http://en.wikipedia.org/wiki/Subset_sum_problem

当然，您可以遍历所有可能的子集以查找总和，但请注意有 (2 ^ CountOfListElements) 个可能的组合。如果列表总是很小，则对其进行编码不会有问题。即使是指数时间解决方案也适用于小集合。

于 2013-05-18T15:48:21.993 回答