For a given Sum and N, print all the combinations

For example if Sum = 16 and N = 2, then the output should be as follows:
0 16
1 15
2 14
3 13
4 12
5 11
6 10
7 9
8 8
9 7
10 6
11 5
12 4
13 3
14 2
15 1
16 0

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int sum = 10;
            int count = 3;
            PrintAllCombinations(sum, count, 0, "");
        }

        public static void PrintAllCombinations(int sum, int count, int depth, string str)
        {
            if(depth == count)
            {
                //Perform validation and return
                if(sum == Sum(str))
                {
                    Console.WriteLine(str);
                }
                return;
            }
            else
            {
                for(int i = 0; i <= sum; i++)
                {
                    PrintAllCombinations(sum, count, depth + 1, str + i.ToString() + " ".ToString());
                }
            }
        }
        public static int Sum (string str)
        {
            Regex reg = new Regex(" ");
            string[] strArray = reg.Split(str.Trim());
            int sum = 0;
            for(int i = 0; i < strArray.Length; i++)
            {
                sum = sum + int.Parse(strArray[i]);
            }
            return sum;
        }
    }
}

Output
=======
0 0 10
0 1 9
0 2 8
0 3 7
0 4 6
0 5 5
0 6 4
0 7 3
0 8 2
0 9 1
0 10 0
1 0 9
1 1 8
1 2 7
1 3 6
1 4 5
1 5 4
1 6 3
1 7 2
1 8 1
1 9 0
2 0 8
2 1 7
2 2 6
2 3 5
2 4 4
2 5 3
2 6 2
2 7 1
2 8 0
3 0 7
3 1 6
3 2 5
3 3 4
3 4 3
3 5 2
3 6 1
3 7 0
4 0 6
4 1 5
4 2 4
4 3 3
4 4 2
4 5 1
4 6 0
5 0 5
5 1 4
5 2 3
5 3 2
5 4 1
5 5 0
6 0 4
6 1 3
6 2 2
6 3 1
6 4 0
7 0 3
7 1 2
7 2 1
7 3 0
8 0 2
8 1 1
8 2 0
9 0 1
9 1 0
10 0 0
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