Combinations Generation using Backtracking Algorithm

Question

I have been working on generating 3 combinations of numbers using the Backtrack Algorithm and I have done thus far the following:

        static int a, b, c;

    static void Combo(int a,int b, int c)
    {
        if (a != 10)
        {
            Combo(a, b, c);
            a++;

        }

            if (b != 10)
            {
                 Combo(a, b, c);
                b++;

            }


        if(c != 10)
        {
                    Combo(a,b,c);
            c++;

        }
        Console.WriteLine("( {0}, {1}, {2})",a,b,c);


    }

And the Main Method:

        static void Main(string[] args)
    {
        Console.WriteLine("Press Any Key to Start Generating xxx number Combination");
        Console.ReadKey();

        Combo(0,0,0);
        Console.WriteLine("Combo function has finished Successfully!");
        Console.ReadKey();


    }

I get a message on cmd saying "Process is terminated due to StackOverFlowException . "

Is there a Problem with my code? If not, could you please help me how to get around this over Flow Problem Note: I want only a recursive backtracking algorithm; I am not looking for anything fancy, creative that is out of my League.

Thanks Forwards!

Sayse · Accepted Answer · 2014-04-19 17:55:42Z

2

Ignore my first comment, you increment a after you call combo, thus your stuck as thusly

static void Combo(int a,int b, int c)
    {
        if (a != 10)
        {
            Combo(a, b, c);
            a++;  <-- This is never reached

a remains at 0 for its lifetime try incrementing during your calls to combo such as

    static void Combo(int a,int b, int c)
    {
        if (a >= 10)
        {
            Combo(++a, b, c);

After further testing, I believe you are after the following (Nested if statements w/ increments):

    static void Combo(int a, int b, int c)
    {
        Console.WriteLine("( {0}, {1}, {2})", a, b, c);
        if (a < 10)
        {
            Combo(++a, b, c);
            if (b < 10)
            {
                Combo(a, ++b, c);
                if (c < 10)
                {
                    Combo(a, b, ++c);
                }
            }
        }
    }

edited Apr 19, 2014 at 17:55

answered Apr 19, 2014 at 17:36

Sayse

43.4k14 gold badges85 silver badges150 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Obzajd Over a year ago

still.. this doesn't give The whole combinations... Do we need to write nested Else statements upon closing each if statement? Does that solves it fully?

Sayse Over a year ago

Try adding the results to a list? It might be a limitation of the console to not be able to show all 1000 results.

Frank Buddha · Accepted Answer · 2014-04-19 19:15:18Z

As suggested by others you're never reaching the line that allows you to increment the counter. Try this algorithm that gives you all "xxx" combinations (000 to 999) and also avoids the generation of duplicates (Sayse's solution generates duplicates):

static void Combo(int a, int b, int c)
{
    if (a < 10)
    {
        if (b < 10)
        {
            if (c < 10)
            {
                Console.WriteLine("( {0}, {1}, {2})", a, b, c);
                Combo(a, b, ++c);
            }
            else
            {
                c = 0;
                Combo(a, ++b, c);
            }
        }
        else
        {
            c = 0; b = 0;
            Combo(++a, b, c);
        }
    }
}

Collectives™ on Stack Overflow

Combinations Generation using Backtracking Algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related