This code follows your thought process when you are asked to generate the answer manually by writing it down on a piece of paper. We keep appending parenthesis following two main rules. For each parenthesis that we want to insert we check if
- we have utilized all the open parenthesis (= n). If we have, we continue by only appending ')' to our solution.
- if we haven't then
1) if each '(' is matched with a ')' , we continue by appending a '('. We cannot add a ')' here as that would break the valid parenthesis rule.
2) if not, we have the option to add either a '(' or ')'. We follow through by appending each of the options and continuing towards generating the result.
Finally, we have a valid result when we have utilized all the ')' . We save the result and return.
Below is the code.
def generate_parenthesis(n) result =  insert_p(result,'', n, 0, 0) result end def insert_p(res, ele, n, num_open_p, num_closed_p) if num_closed_p == n res.push(ele) return end if (num_open_p == n) insert_p(res, ele + ')', n, num_open_p, num_closed_p+1) else if (num_open_p == num_closed_p) insert_p(res, ele + '(', n, num_open_p+1, num_closed_p) else insert_p(res, ele + '(', n, num_open_p+1, num_closed_p) insert_p(res, ele + ')', n, num_open_p, num_closed_p+1) end end end