Saturday, July 19, 2014

Generate Parentheses -- Leetcode

Question:
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Answer:
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n==0) return res;
       
        string s;
        getParenthesis(n, n, s, res);
        return res;
    }
    void getParenthesis(int rr, int lr, string s, vector<string> &res)
    {
        if(rr==0 && lr==0){
            res.push_back(s);
            return;
        }
       
        if(lr>0){
            getParenthesis(rr, lr-1, s+'(', res);
        }
       
        if(rr>lr){
            getParenthesis(rr-1, lr, s+')', res);
        }
    }
};

No comments:

Post a Comment