Combinations to get a given number by adding any numbers greater than zero

For example we have following different ways to make up 5:
1, 1, 1, 1, 1
1, 2, 1, 1
2, 2, 1
3, 1, 1
3, 2
4, 1
5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = 6;
            int sum = 0;
            int start = 1;
            Stopwatch watch = new Stopwatch();
            watch.Start();
            RecursiveSum(num, start, sum, "");
            watch.Stop();
            Console.WriteLine("Elapsed: {0}", watch.Elapsed);
        }

        public static int counter = 0;

        public static void RecursiveSum(int num, int start, int sum, string str)
        {
            if (sum > num)
            {
                return;
            }

            else if (sum == num && num != 0)
            {
                Console.WriteLine(++counter + ". " + str);
                return;
            }

            else
            {
                for (int i = start; i <= num; i++)
                {
                    if (str == "")
                    {
                        RecursiveSum(num, i, sum + i, str + i);
                    }
                    else
                    {
                        if (sum + i <= num)
                        {
                            RecursiveSum(num, i, sum + i, str + ", " + i);
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }
    }
}

Output
=======
1. 1, 1, 1, 1, 1, 1
2. 1, 1, 1, 1, 2
3. 1, 1, 1, 3
4. 1, 1, 2, 2
5. 1, 1, 4
6. 1, 2, 3
7. 1, 5
8. 2, 2, 2
9. 2, 4
10. 3, 3
11. 6
Elapsed: 00:00:00.0015454
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s