CareerCup

pseudoCode :

void generate(string p,int o,int c ,int n)
{
if( o==n && c==n )
{
PRINT(p);
return ;
}

if(c>o)return;

if( o >=c && o<n )
generate(p+'{' ,o+1,c,n );

if( c<o )
generate( p+ '}' ,o,c+1,n );

}

- JD January 25, 2010 | Flag Reply

nice solution.

- spsneo January 25, 2010 | Flag Reply

Can someone explain the solution pls

- Anonymous January 25, 2010 | Flag Reply

nice one

- deaGle January 25, 2010 | Flag Reply

U can look into the catalan number approach. learn to generate catalan numbers through C.

- nikhil January 25, 2010 | Flag Reply

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <assert.h>
#include <algorithm>

using namespace std;

//Q:
//Write a function to generate all possible n pairs of balanced parentheses. For example, if n=1
//{}
//for n=2
//{}{}
//{{}}

void pairs(int);
void pairs(int, int, int, string); //aux function for recursive

int main(int argc, char* argv[])
{
int n = 0;
while(n<=0)
cin>>n;

pairs(n);
return 0;
}

void pairs(int n)
{
pairs(n, n, 0, "");
}

void pairs(int left, int right, int diff, string s)
{
if(left == 0 && right == 0)
{
cout<<s<<endl;
return;
}

if(diff == 0)
{
pairs(left-1, right, diff+1, s+'{');
return;
}
else
{
if(left>0)
pairs(left-1, right, diff+1, s+'{');
pairs(left, right-1, diff-1, s+'}');
}
}

- Bingsuns January 26, 2010 | Flag Reply

Same idea with JD but refine in comparision

void createParentheses(int pos, int length, int open, int close){
		if (close == length){ 
			cout << str << endl;
			return;
		}
		else{
			if (open > close){
				str[pos] = '}';
				createParentheses(pos+1,length,open,close+1);
			}
			if (open < length){
				str[pos] = '{';
				createParentheses(pos+1,length,open+1,close);
			}
		}
	}

Please note that open always >= close

- Silence January 27, 2010 | Flag Reply

Another recursive approach could be in this way:
F(n) = F(i) + F(n - i - 1), for all the i = 1..., n -1

- Anonymous January 27, 2010 | Flag Reply

Any one think about the complexity? These recursive approaches will call the same function multiple times, just link using recursion to solve Fibonacci. like will call generate("", 3, 3, 3) generate("{", 2, 3, 3) generate("{{", 1, 3, 3) generate("{{{", 0, 3, 3) .... **generate("{{}", 1, 2, 3) .... generate("{}", 2, 2, 3) **generate("{}{", 1, 2, 3) .... and if we could save the result of generate("", 1, 2, 3), then just append them to "{{}" and "{}{", the algorithm will run much faster. - Fan January 28, 2010 | Flag Reply

Here's some C# code, based on JD, but simplified. (I believe some cases were unnecessary).

// Call with generate ( "", 0, 0, n );
  static void generate ( string p, int o, int c, int n ) {
    if ( o==n && c==n ) {
      Console.Write ( p ) ;
      return;
    }

    if ( o < n ) {
      generate ( p + '{', o+1, c, n ) ;
    }

    if ( c < o ) {
      generate ( p + '}', o, c+1, n ) ;
    }

    Console.WriteLine (  ) ;
  }

- Anonymous February 02, 2010 | Flag Reply

Here's some C# code, based on JD, but simplified. (I believe some cases were unnecessary).

// Call with generate ( "", 0, 0, n );
  static void generate ( string p, int o, int c, int n ) {
    if ( o==n && c==n ) {
      Console.Write ( p ) ;
      return;
    }

    if ( o < n ) {
      generate ( p + '{', o+1, c, n ) ;
    }

    if ( c < o ) {
      generate ( p + '}', o, c+1, n ) ;
    }

    Console.WriteLine (  ) ;
  }

- Anonymous February 02, 2010 | Flag Reply

wat is the complexity of jd's soln

- spandan February 20, 2010 | Flag Reply

static void Main(string[] args)
{
int n = 5;
breaknext("", n);
Console.ReadLine();
}

static void breaknext(string pre, int n)
{
for (int head = 1; head <= n; head++) {
int next = n - head;
if (next > 1) {
breaknext(pre + deep(head), next);
} else if (next == 0) {
Console.WriteLine(pre + deep(head));
} else if (next == 1) {
Console.WriteLine(pre + deep(head) + deep(next));
}
}
}
static string deep(int deep)
{
string result = "";
for (int i = 0; i < deep; i++) {
result = "{" + result + "}";
}
return result;
}

- masa March 01, 2010 | Flag Reply

Here is my code in C#:

private void GenerateBrackets(int openCount, int closeCount, string str, HashSet<string> bracketList)
        {
            if ((openCount == 0) && (closeCount == 0))
            {
                bracketList.Add(str);
            }

            if ((openCount <= closeCount) && (openCount > 0))
            {
                GenerateBrackets(openCount - 1, closeCount, str + "(", bracketList);
            }
            
            if (closeCount > 0)
            {
                GenerateBrackets(openCount, closeCount - 1, str + ")", bracketList);
            }
        }

        /// <summary>
        /// Given number of brackets, find all permutations of open / close sets
        /// e.g. n = 4, ()()()(), (())(()), ((()))(), (((())))),....
        /// </summary>
        [TestMethod]
        public void BracketCombinations()
        {
            int n = 4;
            HashSet<string> bracketList = new HashSet<string>();
            GenerateBrackets(n, n, string.Empty, bracketList);
        }

- Ashish Kaila March 11, 2011 | Flag Reply