CODEWITHSUNDEEP
algorithmmathrecursionpermutationproof
randomUser47534
randomUser47534

Reputation: 329

Recursive algorithm for pairs of parentheses

I am trying to answer the following question: "Implement an algorithm to print all valid (i.e. properly opened and closed) combinations of n-pairs of parentheses."

The answer says that: "Our first thought might be to apply a recursive approach, where we build the solution for f(n) by adding pairs of parentheses to f(n - 1). We can do this by inserting a pair of parentheses inside every existing pair of parentheses, as well as one at the beginning of the string."

I am having a hard time understanding how we can guarantee that inserting a pair of parentheses inside every existing pair of parentheses, as well as one at the beginning of the string, will create all the possible solutions. How do we know that this won't produce duplicate solutions, or leave out some correct solutions? Could someone please explain?

(Source for quotes: Cracking the Coding Interview)

Upvotes: 2

Views: 1192

Answers (1)

Jason W
Jason W

Reputation: 13179

The approach you described works fine for f(1) and f(2). For n > 2, it will not miss any, but it will generate duplicates.

For f(3), this is when duplicates start being generated. Building on f(2), you have the 2 solutions of "()()" and "(())". When you insert the parenthesis following that algorithm, you end up both of those solutions generating "()(())". You end up with 6 solutions of f(3) instead of the actual 5 because of this duplicate.

If you apply the algorithm to f(5), it generates 33 total solutions of f(1) through f(5). There should only be 22 solutions, so you are getting 10 duplicates there.

There's a very common recursive solution out there involving the counting of multiple parenthesis opening and closing. The best explanation I've seen is at https://anonymouscoders.wordpress.com/2015/06/16/all-balanced-permutation-of-number-of-given-parentheses/

Here's an example of one of the solutions in C:

// Source: http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/
# include<stdio.h>
# define MAX_SIZE 100

void _printParenthesis(int pos, int n, int open, int close);

/* Wrapper over _printParenthesis()*/
void printParenthesis(int n)
{
  if(n > 0)
     _printParenthesis(0, n, 0, 0);
  return;
}     

void _printParenthesis(int pos, int n, int open, int close)
{
  static char str[MAX_SIZE];     

  if(close == n) 
  {
    printf("%s \n", str);
    return;
  }
  else
  {
    if(open > close) {
        str[pos] = '}';
        _printParenthesis(pos+1, n, open, close+1);
    }
    if(open < n) {
       str[pos] = '{';
       _printParenthesis(pos+1, n, open+1, close);
    }
  }
}

/* driver program to test above functions */
int main()
{
  int n = 4;
  printParenthesis(n);
  getchar();
  return 0;
}

For reference, here's a C# version I did for your provided algorithm:

// Initial funtion call
void f(int n)
{
    f(1, n, "");
}

// Recursive call
void f(int n, int max, string output)
{
    for (int i = 0; i < output.Length; i++)
    {
        if (output[i] == '(')
        {
            var inserted = output.Insert(i + 1, "()");
            Console.WriteLine(inserted);
            if (n < max)
                f(n + 1, max, inserted);
        }
    }

    // Pre-pend parens
    output = "()" + output;
    Console.WriteLine(output);
    if (n < max)
        f(n + 1, max, output);
}

f(4);

Link: https://dotnetfiddle.net/GR5l6C

Upvotes: 1

Related Questions