:orphan:

Generate Parentheses
====================

.. highlight:: none

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

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: ["()"]

 

**Constraints:**

- ``1 <= n <= 8``

.. highlight:: python

Pattern
-------
String, Dynamic Programming, Backtracking

Solution
--------
Let's construct a well-formed parentheses string of size 3 from left to right. ::

    (, (), ()(, ()((, ()((), ()(())

Observe that

1. we can only add ')' when the number of '(' is :math:`>` to the number of ')'
2. we can keep adding '(' until we run out.

We can recursively add parenthesis according to these 2 rules until we exhaust
the limit of left and right parentheses.

Code
----

.. literalinclude:: ../problems/medium/generate-parentheses/generate_parentheses__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from generate_parentheses__approach_1 import generateParenthesis
>>> paren = generateParenthesis(3)
>>> set(paren) == {'((()))', '(()())', '(())()', '()(())', '()()()'}
True
>>> generateParenthesis(1)
['()']

Complexity
----------
| Time: :math:`O(4^n / \sqrt{n})` — Catalan number of combinations
| Auxiliary Space: :math:`O(n)` — recursive call stack and string storage

.. autofunction:: generate_parentheses__approach_1.generateParenthesis

.. autofunction:: generate_parentheses__approach_1.genParen