Easy Recursive C++ solution [AC]


  • 0

    The idea is to use recursion to get all permutations of brackets and once we reach the length 'n' we will check for validity. One optimisation that can be done is to maintain the bracket count with each recursion i.e. +1 for '(' and -1 for ')' and when we get a negative count that means it was incorrectly balanced and exit.

    class Solution {
    private:
        vector<string> res;
        void recur(string s, int n, int k)
        {
            if(n<0)
                return;
            if(k<0)
                return;
            if(n==0)
            {
                if(k==0)
                    res.push_back(s);
                return;
            }
            recur(s+"(", n-1, k+1);
            recur(s+")", n-1, k-1);
        }
        
    public:
        vector<string> generateParenthesis(int n) {
            recur("", 2*n, 0);
            return res;
        }
    };```

Log in to reply
 

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