How can I find out which numbers in a defined set add up to another number?

Question

I have a number 6 and now I need to search inside an array of ints if any of the numbers can be added together to get 6.

Example:

1,2,3,5,4 

In the above array I can take 1+2+3 which makes 6.

I can also take 4+2 which is 6.

The question is how do I find those individual numbers that can sum up to the number 6.

Answer 1

One possible option is to get a list of all combinations of items in the array, then check which one of those has the sum of your target number.

I found an extension method for getting the combinations here (copied below).

public static IEnumerable<T[]> Combinations<T>(this IList<T> argList, int argSetSize)
{
    if (argList == null) throw new ArgumentNullException("argList");
    if (argSetSize <= 0) throw new ArgumentException("argSetSize Must be greater than 0", "argSetSize");
        return combinationsImpl(argList, 0, argSetSize - 1);
}

private static IEnumerable<T[]> combinationsImpl<T>(IList<T> argList, int argStart, int argIteration, List<int> argIndicies = null)
{
    argIndicies = argIndicies ?? new List<int>();
    for (int i = argStart; i < argList.Count; i++)
    {
        argIndicies.Add(i);
        if (argIteration > 0)
        {
            foreach (var array in combinationsImpl(argList, i + 1, argIteration - 1, argIndicies))
            {
                yield return array;
            }
        }
        else
        {
            var array = new T[argIndicies.Count];
            for (int j = 0; j < argIndicies.Count; j++)
            {
                array[j] = argList[argIndicies[j]];
            }

            yield return array;
        }
        argIndicies.RemoveAt(argIndicies.Count - 1);
    }
}

Now you just need to call it with the number of combinations you want in your groups. For example, if you wanted to find groups of 2:

List<int> ints = new List<int>() { 1, 2, 3, 4, 5 };
int target = 6;

var combs2 = ints.Combinations(2)
    .Where(x => x.Sum() == target);

This will return 1,5 and 2,4. You can then repeat this up to the maximum number of items you want in a group.

---

If you want to get all the results at once, make a new extension method that will do the unioning for you:

public static IEnumerable<T[]> AllCombinations<T>(this IList<T> argsList)
{
    for (int i = 1; i <= argsList.Count; i++)
    {
        foreach (var combo in argsList.Combinations(i))
        {
            yield return combo;
        }
    }
}

Then you can get all your combinations at once by running

var allCombos = ints.AllCombinations()
    .Where(x => x.Sum() == target);

So for your example, it will return 1,5, 2,4, and 1,2,3 in one collection.

Answer 2

You can find all combinations which results 6 using Lipski's algorithm like this:

static List<List<int>> FindCombinations(int x)
{
    var combinations = new List<List<int>>();
    var P = new int[10];
    var R = new int[10];

    combinations.Add(Enumerable.Repeat(1,x)); // first combination
    P[1] = x;
    R[1] = 1;
    int d = 1, b, sum;

     while (P[1] > 1)
     {
         sum = 0;
         if (P[d] == 1)
         {
            sum = sum + R[d];
            d = d - 1;
         }
         sum = sum + P[d];
         R[d] = R[d] - 1;
         b = P[d] - 1;

         if (R[d] > 0) d++;
         P[d] = b;
         R[d] = sum/b;
         b = sum%b;

         if (b != 0)
         {
            d++;
            P[d] = b;
            R[d] = 1;
         }
         List<int> temp = new List<int>();
         for (int i = 1; i <= d; i++)
            temp = temp.Concat(Enumerable.Repeat(P[i], R[i])).ToList();

         combinations.Add(temp);
    }

    return combinations;
} 

Then all you need to is compare each sequence with your numbers:

 var combinations = FindCombinations(6);
 var numbers = new List<int> {1, 2, 3, 5, 4,6};

 var result =
            combinations.Where(x => x.Intersect(numbers).Count() == x.Count)
                .Select(x => x.Intersect(numbers))
                .ToList();

Here is the result in LINQPad:

Answer 3

If you want to know whether (and discover these numbers) two numbers sum to X it's an easy task and you can do it O(n) on average.

HashSet<int> numbers = new HashSet<int>(yourNumberArray);
foreach(int number in numbers)
  if(numbers.Contains(x-number)) 
     Console.WriteLine(number + " " + "numbers[x-number]");

However when you want to know if x1,x2,...,xk numbers sum to X it's NP-complete problem and no polynominal bounded solution is known (also it is not known does such solution exists). If number of items in your set is small (about ~20-30) you can brute-force your result by enumerating all subsets.

for (int i=1; i< (1 << setSize); ++i)
{
   check does number in current set sum to X by bitwise operations on i 
(treat number binary representation as information about set

 (binary one means item is in set, zero means item is not in set)
}

You can also reduce this problem to knapsack problem and get pseudo-polynominal time, however maximum value in set shouldn't be big. For more information check: http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/