Matching integers in a list

Question

Given I have a list of integers like this:

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1};

and given I have a number, say 13, how will I find the numbers from the list which adds up to 13 using LINQ (or any other way). The list is always in the descending order.

For example: 13 = 10 + 2+ 1, so the linq operation would give me back a list of integers containing 10,2 and 1.

If we cant find the full match as in the case of 24, it's ok for an exception to be generated.

Effort:

  [Test]
        public void Should_find_subset()
        {
            var items = new List<int>() {200, 100, 50, 20, 10, 5, 2, 1};

            var find = 13;
            var result = new List<int>();
            var subset = new List<int>();
            bool found = false;

            foreach (var item in items)
            {
                if (item == find)
                {
                    result.Add(item);
                    found = true;
                }

                if (item < find)
                {
                    subset.Add(item);
                    found = subset.Sum() == find;
                }

                if (found)
                    break;
            }
        }

Thanks,

-Mike

Kind of similar to this question that was asked a few days ago: http://stackoverflow.com/questions/18801466/key-value-pair-list#comment27726961_18801466 . Is there some new online material or something? ;) — Moo-Juice, Sep 20 '13 at 13:31
Nice requirements. Try to post them to [freelancers](http://www.freelancer.com). They will quickly tell you how much implementation costs — Sergey Berezovskiy, Sep 20 '13 at 13:32
@Down voters: Thanks, but I dont know why.I have put the effort now, the question was clear..how to do it using LINQ. — Mike, Sep 20 '13 at 13:48
I think you're looking for the [Knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem) or the [Subset sum problem](http://en.wikipedia.org/wiki/Subset_sum). — the_lotus, Sep 20 '13 at 13:31

Tim Schmelter · Answer 1 · 2013-09-20T15:30:14.403

If i hear combinations i suggest this project: Permutations, Combinations, and Variations

This is working code:

List<int> items = new List<int> { 200, 100, 50, 20, 10, 5, 2, 1 };
var allMatchingCombos = new List<IList<int>>();
for (int i = 1; i < items.Count; i++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(items, i, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 13);
     allMatchingCombos.AddRange(matchingCombos);
}

foreach(var combo in allMatchingCombos)
   Console.WriteLine(string.Join(",", combo));

Output: 10,2,1

Edit: Since you have explicitly asked for LINQ, here is a full LINQified approach:

List<IList<int>> allMatchingCombos = Enumerable.Range(1, items.Count)
    .SelectMany(i => new Combinations<int>(items, i, GenerateOption.WithoutRepetition)
                    .Where(c => c.Sum() == 13)
                    .ToList())
    .ToList();

+1 Ha, how could I forget about that? Let me note that you can also find this library in NuGet, named *Combinatorics Library for .NET* — sloth, Sep 20 '13 at 14:25

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

A simply and inefficient approach using Aggregate:

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1};
var target = 373;

var result = items.Aggregate(new List<int>(), (acc, curr) => 
{
    if (acc.Sum() + curr <= target)
        acc.Add(curr);
    return acc;     
});

if(result.Sum() != target)
    throw new Exception(); // whatever

result:

enter image description here

I should note that such a simply approach will not work for all cases. E.g. List is 68,50,20, and target is 70. This will result in an error instead of 50, 20.

Another inefficient approach that handles such cases:

List<int> items = new List<int> {68, 50, 20};
var target = 70;

var result = new List<int>();
while(result.Sum() != target && items.Any())
{
    result = new List<int>();
    foreach (var item in items)
        if (result.Sum() + item <= target)
            result.Add(item);
    if(result.Sum() != target)
        items.Remove(result.Last());
}

if(result.Sum() != target)
    throw new Exception(); // whatever, no solution found

result:

enter image description here

Using a large input list will probably be slow as hell.

+1 for LinqPad, and I'd give another +1 for `throw new Exception(); // whatever` as it made me think of a programmer who stopped giving a sh*t. :) — Moo-Juice, Sep 20 '13 at 13:37

Matching integers in a list

2 Answers2