How to generate all possibilities of writing a number as a sum of distinct numbers in c#

Question

I'm trying to make a recursive algorithm that returns all possibilities of writing a given number as a sum of distinct numbers. For example, if the given number is 8, my program should return (1,7)(1,2,5)(1,3,4)(2,6)(3,5).

As far as I worked all I could get is (for this example)(1,7)(1,(2,5)(3,4))(2,6)(3,5), and the combinations are even more imbricated as the given number is higher. How can I have the right result instead of mine? The function is:

public String calculate(float number, float i)
    {
        String str = "";
        float half = number / 2;
        while ( i < half)
        {
            float diff = number - i;
            str = str + "(" + i + "," + diff + ")";
            if (calculate(diff, i + 1) != "") 
                str = str + "(" + i + "," + calculate(diff, i + 1) + ")";
            i++;
        }
        return str;
    }

The call of the function is calculate(number,1). Thank you in advance for your help!

I wrote the code in many ways and this one is the closest to the desired result. — Marina Popa, Mar 14 '16 at 21:52
I think the problem does not require recursion, your specific example you have 1 - 8, make a list of integers [1,2,3,4,5,6,7] that contain all the numbers and run through all the possibilities of adding every digit in the list. — Marko, Mar 14 '16 at 22:00
@Marko I have to do this task for school and a recursive algorithm is required. — Marina Popa, Mar 14 '16 at 22:05

score 0 · Accepted Answer · edited May 23 '17 at 12:07

Here's a sample program that I based on a Java answer here on SO. I modified it to display only sums with distinct values, based on your requirements. You can modify it to return a concatenated string, instead of just writing the sums out.

class Program
{
    static void Main(string[] args)
    {
        DisplayDistinctSums(8f);
    }

    static void DisplayDistinctSums(float baseNum)
    {
        DisplayDistinctSums(baseNum, baseNum - 1, "(");
    }

    static void DisplayDistinctSums(float baseNum, float nextNum, string sumString)
    {
        if (baseNum < 1)
        {
            sumString += ")";
            Console.WriteLine(sumString);
            return;
        }

        for (var i = Math.Min(nextNum, baseNum); i >= 1; i--)
        {
            if (!sumString.Contains(i.ToString()))
            {
                DisplayDistinctSums(baseNum - i, i, 
                    sumString.Length == 1 ? sumString + i : sumString + ", " + i);
            }
        }
    }
}

Input: 8

Output:

(7, 1)
(6, 2)
(5, 3)
(5, 2, 1)
(4, 3, 1)

How to generate all possibilities of writing a number as a sum of distinct numbers in c#

1 Answers1