Problem Description:

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:
    vector<string> res;

    void dfs(int n,int left,int right, string str)
    {
        if(left==right&&left==n)
        {
            res.push_back(str);
            return;
        }

        if(left<right||left>n)
            return;
        else
        {
            str+='(';
            dfs(n,left+1,right,str);
            str=str.substr(0,str.size()-1);

            str+=')';
            dfs(n,left,right+1,str);
            str=str.substr(0,str.size()-1);
        }

    }

    vector<string> generateParenthesis(int n) {
        if(n<=0)
            return res;
        string s="";
        dfs(n,0,0,s);
        return res;
    }
};