Generate Parentheses

Problem description:

Given a non negative number n, generate all possible combinations of strings that can be formed by n-pairs of well-formed parentheses, for example:

for n = 2
a solution is: “(())”, “()()”

and for n = 3
a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Solution:

We could use a simple Depth First Search (DFS) approach to recursively build the set of solutions, see the solution code below and then read the explanation:

    void generateParentheses(int n) {
        dfs("", n, n);
    }
    void dfs(String s, int left, int right) // build the set of solutions using DFS approach
    {
        if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
            System.out.println(s);
        if(left > 0) // while we have left parentheses to add, just add them
            dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
        if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
            dfs(s + ")", left, right - 1);
    }

Let’s work on the simplest example to explain how it works:

for n = 2 we know that we have 2 left parentheses and 2 right parentheses so for each recursive call we are going to take 2 decisions:
1.- Can we put a left parentheses?
2.- Can we put a right parentheses?

How do we know if we are able to put a left or right parentheses at each recursive call?
We can put a left parentheses as long as we have at least one left parentheses available but for the right ones we can add them only when we have more right parentheses available because we know that we have already added the corresponding left parentheses before adding the right one.

Do you have any question/comment/suggestion? Please leave your comment below.

Advertisements

2 thoughts on “Generate Parentheses

  1. My brute force solution, it is very demanding.
    set options;
    const int n = 5;
    options.insert(“()”);
    int p = 0;
    for(int i=1;i<n;i++)
    {
    set nove;
    for(auto it = options.begin();it != options.end();it++)
    {
    string s = *it;
    for(int k=0;k<s.length();k++)
    {
    p++;
    string ns = s;
    ns.insert(k, "()");
    nove.insert(ns);
    }
    }
    options = nove;
    }

    for(auto it = options.begin();it != options.end();it++)
    cout << *it << " ";
    cout << "total created " << p <<" unique " << options.size() << endl;

  2. Hey everyone, this is my C implementation of the above problem statement. Enjoy!!!

    // Program to print the balanced set of paranthesis

    #include
    #include
    #include

    void printParenthesis(char*,int,int,int,int);
    void printArray(char*,int);

    int main(){
    int n;
    char*arr;
    scanf(“%d”,&n);
    arr = (char*)calloc(2*n,sizeof(char));
    printParenthesis(arr,0,n,n,n);
    return 0;
    }

    void printParenthesis(char* arr,int ind,int open,int close,int n){
    if(ind == 2*n-1){
    arr[ind] = ‘)’;
    printArray(arr,2*n);
    }
    if(open>0){
    arr[ind] = ‘(‘;
    printParenthesis(arr,ind+1,open-1,close,n);
    }
    if(close>open){
    arr[ind] = ‘)’;
    printParenthesis(arr,ind+1,open,close-1,n);
    }
    }

    void printArray(char* arr,int total){
    int i;
    for(i=0;i<total;++i){
    printf("%c",arr[i]);
    }
    printf("\n");
    }

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