All combinations of balanced parentheses (Generate Parentheses)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Thoughts:
Recursion. Base case is which the solution has size of 2*n. Recursive step: each time we count number of open parenthesis and closed parenthesis. If open == closed, then we have to add open parenthesis. If open > closed, we can add open parenthesis as long as we do not exceed n. We can also add closed parenthesis.

Code (Java):

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> solutions = new ArrayList<String>();
        recursion(n, new String(), solutions);
        return solutions;
    }

    private void recursion(int n, String str, ArrayList<String> sol) {
        if(str.length() == 2 * n)
            sol.add(str);
        else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < str.length(); ++i) {
                if(str.charAt(i) == '(')
                    left++;
                if(str.charAt(i) == ')')
                    right++;
            }
            if(left == right)
                recursion(n, str + "(", sol);
            else if(right < left) {
                if(left < n)
                    recursion(n, str + "(", sol);
                recursion(n, str + ")", sol);
            }
        }
    }
}

Code (C++):

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> solutions;
        string solution;
        recursion(n, solution, solutions);
        return solutions;
    }

    void recursion(int n, string solution, vector<string> &solutions) {
        if(solution.size() == 2*n) {
            solutions.push_back(solution);
        } else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < solution.size(); ++i) {
                if(solution[i] == '(')
                    left++;
                if(solution[i] == ')')
                    right++;
            }
            if(left == right)
                recursion(n, solution + "(", solutions);
            else if(left > right) {
                if(left < n)
                    recursion(n, solution + "(", solutions);
                recursion(n, solution + ")", solutions);
            }
        }
    }
};
Advertisements

1 Comment (+add yours?)

  1. Poonam
    Feb 17, 2014 @ 06:07:10

    Another way to solve this would be

    public class Parenthesis {

    public static void main(String[] args) {
    int n = 3;
    char[] str = new char[n*2];
    printParenthesis(n,n,str,0);
    }

    private static void printParenthesis(int lCount, int rCount, char[] str,
    int count) {
    if(lCount < 0 || rCount 0){
    str[count] = ‘(‘;
    printParenthesis(lCount-1, rCount, str, count+1);
    }
    if(rCount > lCount){
    str[count] = ‘)’;
    printParenthesis(lCount, rCount-1, str, count+1);
    }
    }
    }
    }

    Reply

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

%d bloggers like this: