-3
void solve(int n,int open,int close,string s,vector<string>&ans) {
    if(open==close && close==n) {
        ans.push_back(s);
        return;
    }
    if(open<n) {
        s+="(";
        solve(n,open+1,close,s,ans);
        s.pop_back();
    }
    if(open>close) {
        s+=")";
        solve(n,open,close+1,s,ans);
        s.pop_back();
    }
}
vector<string> generateParentheses(int n) {
    vector<string> ans;
    solve(n,0,0,"",ans);
    return ans;
}

This piece of code generates all possible permutations of parantheses for a given value n. I can easily dry run the code when n=2 and reach to the output "(())". But I really don't understand how it reaches to "()()".

The point where I get stuck is "()". The code can't close the bracket till the no of opening brackets is equal to n.

vagabond
  • 1
  • 1
  • 9
    Run your code in a debugger and step through it? – Botje Mar 08 '23 at 14:06
  • 6
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Jason Mar 08 '23 at 14:08
  • From what I can tell, all you need is `else if` for the `if (open > close)` statement. – B Remmelzwaal Mar 08 '23 at 14:11
  • what is "dry run" ? I have read this several times, but till now I didnt get a reply to what it means. – 463035818_is_not_an_ai Mar 08 '23 at 14:18
  • It reaches _both_ `(())` and `()()`. Isn't that what you designed the code to do? – Ted Lyngmo Mar 08 '23 at 14:23
  • 1
    *"The code can't close the bracket till the no of opening brackets is equal to n."* -- false, hence your confusion. When things don't make sense, question your assumptions. – JaMiT Mar 08 '23 at 14:54
  • @463035818_is_not_a_number *"what is 'dry run' ?"* -- I believe this means walking through the code by hand. – JaMiT Mar 08 '23 at 14:57
  • Adding some debug output will ease understanding the flow of the program: https://godbolt.org/z/o8v5bz1oT – rturrado Mar 08 '23 at 15:14

1 Answers1

1

After "()", open is 1, close is 1, n is 2.

It will enter:

if(open<n) {
    s+="(";
    solve(n,open+1,close,s,ans);
    s.pop_back();
}

effectively going to "()(". You should be able to trace the rest from here.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42