parens.py

def generate_parens(n):
    # this is a map from (n_unclosed, n_left) to result.
    results = {}

    def _generate_parens(n_unclosed, n_left):
        # if we have a memoized value already, use it
        already_computed = results.get((n_unclosed, n_left), None)
        if already_computed is not None:
            return already_computed

        # This function returns a list of all possibilities given its inputs.
        if n_left == 0:
            # if we don't have any )'s left, generate as many ) as we need
            return [ ")" * n_unclosed ]

        # prepend a ( to every result of the recursive call
        result = ["(" + x for x in _generate_parens(n_unclosed + 1, n_left - 1)]
        if n_unclosed > 0:
            # if we can close any, prepend a ) to every result.
            result.extend([")" + x for x in _generate_parens(n_unclosed - 1, n_left)])

        # memoize the result
        results[(n_unclosed, n_left)] = result
        return result

    return _generate_parens(0, n)