Найдите элементы в списке, которые вместе суммируют до целевого номера

Предположим, у меня есть список:

List _arr = new List {1, 3, 4}; 

И цель 4

Я хочу вернуть {1, 3} как 1 + 3 = 4 и {4} как 4 = 4 используя linq из данного списка.

Как я могу это сделать?

Это легко, если у нас есть способ получить все подмножества перечислителя / списка
(найти здесь: Ответ: Самый элегантный способ получить все подмножества массива в 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> SubSetsOf(this IEnumerable 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(), 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 

Я считаю, что лучшим решением этой проблемы является динамическое программирование .

Создайте 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[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 с

  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, потому что что-то говорит мне, что это будет потрясающе. 😉

Если вы после действительно хорошего и быстрого решения этой проблемы, вы не одиноки.

Это хорошо известная проблема SUBSET SUM. Я предлагаю вам ознакомиться с Википедии здесь:

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

Конечно, вы можете перебирать все возможные подмножества, ища свою сумму, но помните, что есть (2 ^ CountOfListElements) возможные комбинации. Если список всегда мал по размеру, у вас не будет проблем с его кодированием. Даже экспоненциальное временное решение будет работать для небольших наборов.