0

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!

4
  • 3
    A while loop in a recursive call doesn't seem right. Mar 14, 2016 at 21:51
  • I wrote the code in many ways and this one is the closest to the desired result. Mar 14, 2016 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, 2016 at 22:00
  • @Marko I have to do this task for school and a recursive algorithm is required. Mar 14, 2016 at 22:05

1 Answer 1

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.