C++ 0ms solution DFS + backtracking


  • 2
    C
    class Solution {
    public:
    
        vector<string> generateParenthesis(int n) 
        {
            string strr;
            vector<string>  allParens;
            genParethesisUtil(0, 0, n, allParens, strr);
            
            return allParens;
        }
        
        void genParethesisUtil(int left, int right, int n, vector<string> & allParens, string strr)
        {
    
            if(right == n)
            {
    
                allParens.push_back(strr);
                return;
            }
            
            if(left < n)
            {
                strr += '(';
                genParethesisUtil(left + 1, right, n, allParens, strr);
                strr.pop_back();
            }
            
            //if left is smaller than right then add an )
            if(left > right)
            {
                strr += ')';
                genParethesisUtil(left, right + 1, n, allParens, strr);
                strr.pop_back();
            }
            
        }
    };

Log in to reply
 

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