An easy-understood answer with comments. Only valid parentheses are constructed


  • 0
    J

    The core idea is that the number of '(' should always be more than the number of ')' if we count from left to right

    vector<string> generateParenthesis(int n) {
        vector<string> res = construct(0,0,n);
        return res;
     }
    
    vector<string> construct(int c1, int c2, int n)  // c1 for the number of '(', c2 -> ')'
    {
    	vector<string> ret;
    	if (c1 < c2)    // '(' less than ')', invalid
    		return ret;
    	else if (c1 == c2)  // '(' equal to ')', must add '('
    	{
    		if (c1 >= n)
    			return ret;
    		vector<string> res = construct(c1+1,c2,n);
    		for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
    			ret.push_back('('+*it);
    		return ret;
    	}
    	else if (c1 < n)  // '(' more than ')', add '(' or ')'
    	{
    		vector<string> res = construct(c1+1,c2,n);  //  add '('
    		for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
    			ret.push_back('('+*it);
    			
    		res = construct(c1,c2+1,n);  //  add ')'
    		for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
    			ret.push_back(')'+*it);
    		return ret;
    	}
    	else   // number of '(' is equal n, must add ')';
    	{
    		vector<string> res = construct(c1,c2+1,n);
    		for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
    			ret.push_back(')'+*it);
    
    		if (!res.size())
    			ret.push_back(")");
    		return ret;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.