Generate Parentheses

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

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

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

const generateParenthesis = function (n) {
  const res = [];
  generate(n, n, "", n, res);
  return res;
};

const generate = (left, right, temp, n, res) => {
  if (temp.length === 2 * n) {
    res.push(temp);
    return;
  }

  if (left > 0) {
    generate(left - 1, right, temp + "(", n, res);
  }

  // can place right only if left is already placed
  if (right > left) {
    generate(left, right - 1, temp + ")", n, res);
  }
};

")" can only chosen when their "remaining" pool is bigger than "(". Which means more "(" have been used already as compared to ")", now it's okay to pick ")" to complete valid parenthesis.

At any moment or choice, number of ")" used cannot be more than "(" used.

()) -> Wrong! The choice of last ")" is wrong because the number of ")" used is now more than "(" used.

// Good stack based solution to avoid recursion
const generateParenthesis = function (n) {
  const res = [];
  const stack = [["(", 1, 0]];

  // these open and close are the count of each that are already
  // used/added to the curRes string.
  while (stack.length) {
    const [curRes, open, close] = stack.pop();

    if (curRes.length === 2 * n) {
      res.push(curRes);
      continue;
    }

    if (open < n) {
      stack.push([curRes + "(", open + 1, close]);
    }

    if (open > close) {
      stack.push([curRes + ")", open, close + 1]);
    }
  }

  return res;
};