leetcode Generate Parentheses

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

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:

"((()))", "(()())", "(())()", "()(())", "()()()"


The title is given contains n on bracket sequence and can match. Of course, the general idea is the whole arrangement and judgment, whether satisfies the matching. Each place '(' or ')' because it is occurring in pairs, so it can be seen that the n '(' in the 2*n position. It consists of C (n, 2n), and then determine whether matching. The time complexity is O (n) can detect whether matching. This idea more trouble, should still be feasible. . . .

Say something I do it, is DFS, it is easy to think of it, just put these brackets into a position to go up, the remaining two variables recorded '(' and ')' the number of brackets, remember to do(lc,rc).

Each to a position on the brackets, and only two cases, while lc> 0 ( .

When the rc> 0 and rc> LC).

Because if the rest of the bracket is equal to the number of only '(' otherwise do not match, as long as the lc> 0 can put '(', because in front of the matching. The key in can put ')' only has been placed in front of the '(' to 'put'). Rc> LC already put more(.


class Solution {
public:
    vector<string >  vec;
    void dfs(string &temp,int l,int r)
    {
    if(!l&&!r)
    {
        vec.push_back(temp);
        return ;
    }
    if(l)
    {
        int n=temp.size();
        temp.push_back('(');
        dfs(temp,l-1,r);
        temp.resize(n);
    }
    if(r&&(r>l))
    {
        temp.push_back(')');
        dfs(temp,l,r-1);
    }
    }
    vector<string> generateParenthesis(int n) {
        vec.clear();
        string t;
        dfs(t,n,n);
        return vec;
    }
};

If there is not the right place, please.


Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Malcolm at December 17, 2013 - 5:09 PM