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?

you have much to specify concerning the rules you must follow. I assume "numbers" means integers greater than 0. I assume result sets are un-ordered, i.e., {1,2} == {2,1}. This would imply your second parameter may never be less than your first. Do I understand your requirements right? — Les, Apr 23 '14 at 18:48
If i assign to numbercount parameter as 3, algorithm finds the target integer with using 3 ints in addition process. In first example: 1+1+7, 1+2+6,1+3+5,1+4+4,2+2+5,2+3+4,3+3+3 (additions includes 3 ints) — T.Y. Kucuk, Apr 23 '14 at 18:56

score 2 · Accepted Answer · edited May 23 '17 at 12:28

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.

score 0 · Answer 2 · answered Apr 27 '14 at 18:38

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

            }

        }

    }

}

}

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

2 Answers2