0 ms c++ recursive


  • 0
    K
    void generateParenthesis(vector<string> &vec, string str, int lt, int rt, int count) {
        if(lt<0 || rt<lt) return;
        if(lt==0 && rt==0) {
            vec.push_back(str);
        } else {
            if(lt>0){
                generateParenthesis(vec,str+"(",lt-1,rt,count+1);
            }
            if(rt>lt) {
               generateParenthesis(vec,str+")",lt,rt-1,count+1);
            }
        }
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> par;
        string str;
        str.reserve(n*2);
        int count =0;
        generateParenthesis(par,str,n,n,count);
        return par;
    }

  • 0
    G

    What is count doing here?


  • 0
    K

    Count is to keep track of the total parentheses added so far (i.e. the position in the output string where the new parentheses is to be added).
    Code is creating the parentheses one by one untill all the permissible left and right parentheses are used up. so, the two parameters passed lt & rt are remaining left and right parentheses respectively. There are two conditions when additional parantheses can be added -

    1. Left : when there is any (>0) left par is remaining (still to be added)
    2. Right : when number of right remaining is greater than number of left remaining (i.e. more left has been used already)
      I hope this clarifies.

Log in to reply
 

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