LC 22. Generate Parentheses

The problem

Solution

This question was the first recursion problem I'd done in a while, so it was pretty tricky to solve. I needed a hint on the best way to keep track of the numbers of opening and closing parentheses. Using a counter seems simple now, but I was initially overthinking it by trying to count on each call of addParentheses.

To work through recursion, it helps me to draw out the evolution of the values. I drew this on my iPad at first, but made the cleaner version below for the blog:

After adding the first opening parentheses, openings and closings are added where possible until the string hits the target length, n * 2. Blue arrows indicate where only one can be added due to either requiring an opening or running out of openings. An opening would be required when the previous openings are all paired up such that the number of openings equals the number of closings (like in the rightmost branch). Another way to word it is adding a closing makes the pairs invalid. On the other hand, when all openings are added, closings are added for every recursive call afterward (the leftmost branch).

function generateParenthesis(n: number): string[] {
  let answer = []

  const addParentheses = (str: string, open: number, close: number) => {
    if (str.length === n * 2) {
      answer.push(str)
    }

    if (open < n) {
      addParentheses(str + '(', open + 1, close)
    }

    if (close < open) {
      addParentheses(str + ')', open, close + 1)
    }
  }
  addParentheses('', 0, 0)
  return answer
}