C++ solution accepted in 3ms


  • 3
    E

    The basic idea of this solution is DFS.

    But two questions are needed to solve:

    1. How many left and right braces have been used separately?

    2. Is this a valid string?

    The first one is solved by maintaining two variables named as"left" and"right" to track the usage of braces. Detect invalid results in early time.

    The second one is solved by maintaining a variables named as "sum", sum should always be at least zero, if we define left brace as one, and right brace as negative one.

    class Solution {
    vector<string> *res;
    int num; 
    
    
    private:
    void dfs(int left, int right, string cur, int sum){
        if(left == num && right == num){
            (*res).push_back(cur);
            return; 
        }
        if(left != num )//no need to check left brace 
            dfs(left+1, right, cur+"(", sum + 1);
        if(right != num && sum - 1 >= 0)
            dfs(left, right+1, cur+")", sum -1);
        
    }
    
    public:
    vector<string> generateParenthesis(int n) {
    	vector<string> _res;
    	if(!n) return _res;
    	this->res = &_res;
    	this->num = n;
    	dfs(1,0,"(", 1);//left is one, right is -1
    	return (*res);
     
    }
    

    };


Log in to reply
 

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