0022. Generate Parentheses.md

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

---

Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1 Output: ["()"]

---

3 3 => 2 3 => 1 3 => 0 3 => 0 2 => 0 1 => 0 0  res: ['((()))']    
1 3 => 1 2 => 0 2 => 0 1 => 0 0 res: ['((()))', '(()())']  
1 2 => 1 1 => 0 1 => 0 0  res: ['((()))', '(()())', '(())()']  
1 1 => 1 0 RETURN because l > r, not a parenthesis 

2 3 => 2 2 => 1 2 => 0 2 => 0 1 => 0 0  res: ['((()))', '(()())', '(())()', '()(())']  
1 2 => 1 1 => 0 1 => 0 0  res: ['((()))', '(()())', '(())()', '()(())', '()()()']  
1 1 => 1 0   RETURN because l > r, not a parenthesis   

2 2 => 2 1  RETURN because l > r, not a parenthesis  

3 3 => 3 2 RETURN because l > r, not a parenthesis  

return res: ['((()))', '(()())', '(())()', '()(())', '()()()']  

T.C.

O(n^2n). Space should be O(n)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let stack = [];
    
    function explore(l, r, s) {
        if(l > r) return;
        if(l === 0 && r === 0) {
            stack.push(s);
            return;
        }
        if(l > 0) {
            explore(l - 1, r, s + '(');
        }
        if(r > 0) {
            explore(l, r - 1, s + ")");
        }
    }
    
    explore(n, n, "");
    return stack;
};