CODEWITHSUNDEEP
c#linq
Mike
Mike

Reputation: 3294

Matching integers in a list

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

Upvotes: 2

Views: 213

Answers (2)

Tim Schmelter
Tim Schmelter

Reputation: 460360

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

Upvotes: 4

sloth
sloth

Reputation: 101162

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.

Upvotes: 3

Related Questions