Simple 2ms c++ solution with explanation


  • 25
    X

    class Solution {
    public:

    vector<string> result;
    vector<string> generateParenthesis(int n) {
        helper("", n, 0);
        return result;
    }
    
    /*  this hepler function insert result strings to "vector<string> result"
    	When number of '(' less than "n", can append '(';
    	When number of '(' is more than number of ')', can append ')';
    
    	string s : current string;
    	int leftpare_need : number of '(' that have not put into "string s";
    	int moreleft : number of '(' minus number of ')' in the "string s";
    */
    
    void helper(string s, int leftpare_need, int moreleft)
    {
    	if(leftpare_need == 0 && moreleft == 0)
    	{
    	    result.push_back(s);
    	    return;
    	}
    	if(leftpare_need > 0)
    		helper(s + "(", leftpare_need - 1, moreleft+1);
    	if(moreleft > 0)
    		helper(s + ")", leftpare_need, moreleft - 1);
    }
    

    };


  • 2
    E

    excellent!!!
    how could you figure this beautiful code out is beyond my mind


  • 0
    R

    some similar solution.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
        	vector<string> ret;
        
        	backTrackingFun(n,n,"",ret);
        	return ret;
        }
        
        void backTrackingFun(int lefts, int rights, string r, vector<string> &ret){
        	if(0==lefts && 0==rights){
        		ret.push_back(r);
        		return;
        	}
        
        	if(lefts>0){
        		r.push_back('(');
        		backTrackingFun(lefts-1,rights,r,ret);
        		r.pop_back();
        	}
        
        	if(rights>lefts){
        		r.push_back(')');
        		backTrackingFun(lefts,rights-1,r,ret);
        		r.pop_back();
        	}
        }
    };

  • 4
    S

    Piaoliang! why u so diao!


Log in to reply
 

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