Finding if a target number is the sum of two numbers in an array via LINQ

Question

A basic solution would look like this:

bool sortTest(int[] numbers, int target)
{
    Array.Sort(numbers);
    for(int i = 0; i < numbers.Length; i++)
    {
       for(int j = numbers.Length-1; j > i; j--)
       {
           if(numbers[i] + numbers[j] == target)
               return true;
       }
    }
    return false;
}

Now I'm very new to LINQ but this is what I have written so far:

var result = from num in numbers
             where numbers.Contains(target -num)
             select num;
if (result.Count() > 0)
    return true;

return false;

Now i'm running into an issue given the following example:
Array: 1, 2, 4, 5, 8
Target: 16

It should return back false, but it's catching 16-8=8. So how do I go about not letting it notice itself in the contains check? Or can I make a second array each time within the query that doesn't contain the number I'm working with(thus solving the problem)?

Thanks in advance.

Answer 1

Is this what you're looking for?

var result = from n1 in numbers
             from n2 in numbers
             where n1 != n2 && n1 + n2 == target
             select new { n1, n2 };

[Edit] This returns matches twice and ignores the situation where a number is duplicated in the array. You can't handle these situations using Expression Syntax because you can't access the index of a matched item, but you can do it like this:

var result = numbers.Select((n1, idx) => 
    new {n1, n2 = numbers.Take(idx).FirstOrDefault(
    n2 => n1 + n2 == target)}).Where(pair => pair.n2 != 0);

As long as you don't have any zeros in your array.

[Further thought Edit]

The perfect mix solution:

var result = from item in numbers.Select((n1, idx) =>
                 new {n1, shortList = numbers.Take(idx)})
             from n2 in item.shortList
             where item.n1 + n2 == target
             select new {n1 = item.n1, n2};

Answer 2

To improve on pdr's reply and address the concerns mentioned in the comments you could use the overloaded Select method to compare the indices of the items and ensure uniqueness.

public bool sortTest(int[] numbers, int target)
{
    var indexedInput = numbers.Select((n, i) => new { Number = n, Index = i });

    var result = from x in indexedInput
                 from y in indexedInput
                 where x.Index != y.Index
                 select x.Number + y.Number == target;

    return result.Any(item => item);
}

Or in dot notation:

var result = numbers.Select((n, i) => new { Number = n, Index = i })
                    .SelectMany(
                        x => indexedInput,
                        (x, y) => new { x = x,  y = y })
                    .Where(item => item.x.Index != item.y.Index)
                    .Select(item => item.x.Number + item.y.Number == target);

Answer 3

What I'd do to solve this problem in general is first write a "chooser".

public static IEnumerable<IEnumerable<T>> Chooser<T>(this IList<T> sequence, int num)
{ ... left as an exercise ... }

The output of the chooser is a sequence of sequences. Each sub-sequence is of length num, and consists of elements chosen from the original sequence. So if you passed { 10, 30, 20, 50 } as the sequence and 3 for num, you'd get the sequence of sequences:

{10, 30, 20}, {10, 30, 50}, {10, 20, 50}, {30, 20, 50}

as a result.

Once you've written Chooser, the problem becomes easy:

var results = 
  from subsequence in numbers.Chooser(2)
  where subsequence.Sum() == target
  select subsequence;

And now you can solve the problem for subsequences of other sizes, not just pairs.

Writing Chooser is a bit tricky but it's not too hard.