Algorithm to find all addition combination of a number with specific number sets?

Question

I have a problem that is about addition combinations of numbers.

For example, i have a function which takes 2 integer parameters to find all addition combinations of given parameter.

To illustrate:

public List<List<int>> getcombinations(int numbercount, int target){
....
return List;
}

Let's determine the arguments by making up:

numbercount=3 //it will be calculated with 3 integers
target=9 // final number to find

The output of the function is supposed to be in this way:

{{1,1,7},{1,2,6},{1,3,5},{1,4,4},{2,2,5},{2,3,4},{3,3,3}}

Our target number can be found with 7 possibilities when 3 integers is used in addition.

One more example:

numbercount=2
target=7
//Output should be like this:
{{1,6},{2,5},{3,4}} // 3 possibilities when 2 integers is used in addition. 

I tried to find a solution for this problem. But I could not find a way to solve it. What do you advise to search or learn about to solve it?

Answer 1

This should be a starting point, refine as necessary, read related link for awesome explanation about generating combinations.

 class Program
{
    static void Main(string[] args)
    {
        foreach (var set in GetCombinations(3, 9))
        {
            Console.WriteLine("{{{0}}}", string.Join(",", set));
        }
        Console.ReadKey();
    }


    public static IEnumerable<IEnumerable<int>> GetCombinations(int length, int targetSum)
    {
        var combinations = Enumerable.Range(1, length)
            .Select(x => Enumerable.Range(1, targetSum - length+1)).CartesianProduct();
        combinations=combinations
            .Where(x => x.Sum(y => y) == targetSum);

        return combinations.Distinct(new Comparer()).ToList();
    }

}

public class Comparer : IEqualityComparer<IEnumerable<int>>
{

    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        var isEqual= x.OrderBy(a => a).SequenceEqual(y.OrderBy(b => b));
        return isEqual;
    }

    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(); //lazy me, just indicate collection is same if their sum is same.
    }
}

public static class Extensions
{
   public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item }));
    }
}

The extension method for generating combinations is a famous masterpiece from Eric Lippert.

Answer 2

This code is notably faster:

using System;
using System.Collections.Generic;


namespace konsol
{
class Program
{

    private static List<List<int>> combinations = new List<List<int>>();

    private static void Main(string[] args)
    {

        int length = 4
        Generate(length , 10, 0, 1, 0, new int[length]);


        foreach (var varibles in combinations)
        {
            Console.WriteLine(String.Join(",", variables));
        }

        Console.ReadKey();
    }



    private static void Generate(int length, int target, int k, int last, int sum, int[] a)
    {

        if (k == length- 1)
        {

            a[k] = target - sum;
            combinations.Add(new List<int>(a));

        }
        else
        {

            for (int i = last; i < target - sum - i + 1; i++)
            {

                a[k] = i;
                Generate(length, target, k + 1, i, sum + i, a);

            }

        }

    }

}

}