22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

Python

Backtracking

• Time:

$$O\left(\frac {1} {1+n} {2n \choose k}\right) = O\left(\frac {4^n} {n\sqrt{n}}\right)$$

• Space:

$$O\left(\frac {4^n} {n\sqrt{n}}\right)$$

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        def backtrack(track: List[str], left: int, right: int):
            if left == right and left == n:
                result.append(''.join(track))
                return

            if left < n:
                track.append("(")
                backtrack(track, left+1, right)
                track.pop()

            if right < left:
                track.append(")")
                backtrack(track, left, right+1)
                track.pop()

        backtrack([], 0, 0)
        return result

Javascript

var generateParenthesis = function(n) {
  const result = [];

  var backtrack = function(open, close, track = []) {
    if (open === close && open === n) {
      result.push(track.join(''));
      return;
    }

    if (open < n) {
      track.push('(');
      backtrack(open + 1, close, track);
      track.pop();
    }

    if (close < open) {
      track.push(')');
      backtrack(open, close +1, track);
      track.pop();
    }
  }

  backtrack(0,0);

  return result;
};