How to find the Big-O for finding combinations of balanced parentheses?
Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses.

Bertrand's formula states that for each $a$, the number of such arrangements is
$$
\frac{(a+1)-(k-a)}{k+1} \binom{k+1}{a+1} = \binom{k}{a} - \binom{k}{a+1}.
$$
Hence the number of nodes at level $k$ is
$$
\sum_{\lceil k/2 \rceil \leq a \leq \min(k,n)} \left[\binom{k}{a} - \binom{k}{a+1}\right] = \binom{k}{\lceil k/2 \rceil} - \binom{k}{\min(k,n)+1}.
$$
Summing this for $k$ from $0$ to $2n$, we obtain
$$
\sum_{k=0}^n \binom{k}{\lceil k/2 \rceil} + \sum_{k=n+1}^{2n} \left[\binom{k}{\lceil k/2 \rceil} - \binom{k}{n+1}\right].
$$
It follows from Stirling's approximation that this is $O(4^n/\sqrt{n})$, and conversely, just considering $k = 2n$ (corresponding to Catalan numbers), this is $\Omega(4^n/n^{1.5})$.

We are however not done, since the numbers involves are quite large &mdash; on the order of $n$ bits. Therefore arithmetic takes super-constant time. We still get a running time of $\tilde{O}(4^n)$.

Now for space complexity. The recursion tree is $n$ levels deep, and at each level we might be storing up to $n$ bits of information, giving an upper bound of $O(n^2)$ bits. This should be quite tight.