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:

"((()))", "(()())", "(())()", "()(())", "()()()"
*/



class Solution {
public:

    void helper(int l, int r, string pair, int n, vector<string>& res)
    {
        if (l == r && l == n)
        {
            res.push_back(pair);
            return;
        }
        
        if (l < n)
            helper(l + 1, r, pair+'(', n, res);
        if (r < l)
            helper(l, r + 1, pair+')', n, res);
    }
    
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<string> res;
        
        if (n <= 0) return res;
        
        helper(0, 0, "", n, res);
        
        return res;
    }
};
Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s