Algorithm to Print All Valid Combations of N Pairs of Parenthesis

Calculating the complexity of algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses

Let's try with a simpler version instead.

Some theorems:

1. Properly paired string are of even length. Don't ask me to prove this one, please.
2. Given a properly paired string of length 2k, it is possible to construct all strings of length 2(k + 1) by inserting pairs of parenthesis '()' at every possible location within the string. There are 2k + 1 such positions.
3. To generate all n pairs, we need to recursive into the insertion step n times (and get strings of length 2n.

Note that this is not enough to generate all unique properly paired strings, because e.g. inserting () into () yields the same string twice (()()). However as an upper bound it should suffice.

def add_parens(s, nparens):    
    if not s:    
       add_parens('()', nparens)    
    max_length = 2 * nparens    
       if len(s) == max_length:    
       print(s)    
    else:    
        for i in range(0, len(s)):    
            add_parens(s[0:i] + '()' + s[i:], nparens)    

n = 5      
add_parens('', n)  

Time complexity:

1. There is 1 insertion point for the empty string.
2. There are 3 insertion points for ().
   ...

So all in all:

T(n) = 1 * 3 * ... * 2n + 1 ~ O(n!)

Space complexity for the recursive version is O(n(2n + 1)), however I'm pretty sure it is possible to bring this down to linear.

Generate all balanced parenthesis for a given N

//c++ program to print all the combinations of 
balanced parenthesis.
#include <bits/stdc++.h>
using namespace std;
//function which generates all possible n pairs 
of balanced parentheses.
//open : count of the number of open parentheses 
used in generating the current string s.
//close : count of the number of closed 
parentheses used in generating the current string 
s.
//s : currently generated string/
//ans : a vector of strings to store all the 
valid parentheses.
void generateParenthesis(int n, int open, int 
close, string s, vector<string> &ans){
  //if the count of both open and close 
parentheses reaches n, it means we have generated 
a valid parentheses.
  //So, we add the currently generated string s 
to the final ans and return.
if(open==n && close==n){
    ans.push_back(s);
    return;
}  
  //At any index i in the generation of the 
string s, we can put an open parentheses only if 
its count until that time is less than n.
if(open<n){
    generateParenthesis(n, open+1, close, s+"{", 
ans);
}
//At any index i in the generation of the string             
s, we can put a closed parentheses only if its 
count until that time is less than the count of 
open parentheses.
if(close<open){
    generateParenthesis(n, open, close+1, s+"}", 
ans);
}
  
}
int main() {
int n = 3;
  //vector ans is created to store all the 
possible valid combinations of the parentheses.
vector<string> ans;
  //initially we are passing the counts of open 
and close as 0, and the string s as an empty 
string. 
generateParenthesis(n,0,0,"",ans);
  //Now, here we print out all the combinations.
for(auto s:ans){
    cout<<s<<endl;
}
return 0;
}

What's the time complexity of this parentheses combination?

The precise number of output lines is equal to the Catalan numbers: https://en.m.wikipedia.org/wiki/Catalan_number. The nth Catalan number is Theta(4^n/n^(3/2)), so the running time is Theta(4^n/√n).

Time complexity for combination of parentheses

The complexity of this code is O(n * Cat(n)) where Cat(n) is the nth Catalan number. There are Cat(n) possible valid strings that are valid combinations of parenthesis (see https://en.wikipedia.org/wiki/Catalan_number), and for each a string of length n is created.

Since Cat(n) = choose(2n, n) / (n + 1), O(n * Cat(n)) = O(choose(2n, n)) = O(4^n / sqrt(n)) (see https://en.wikipedia.org/wiki/Central_binomial_coefficient).

There's two main flaws with your reasoning. The first is that the search tree is not balanced: the tree that you search when you close the right brace is not the same size as the tree you search when you add another left brace, so more common methods for computing complexity don't work. A second mistake is that even if you assume the tree is balanced, the height of the search tree would be n, and the number of leaves found O(2^n). This differs from analysis of a binary search tree, where you usually have n things in the tree and the height is O(log n).

I don't think there's any standard way to compute the time complexity here -- ultimately you're going to be reproducing something like the math done when you count valid parenthetical strings -- and the Master theorem isn't going to power you through that.

But there is a useful insight here: if a program generates f(n) things, and the cost of generating each if c(n), then the program's complexity can't be better than O(c(n)f(n)). Here, f(n) = Cat(n) and c(n) = 2n, so you can quickly get a lower bound for the complexity even if analyzing the code is difficult. This trick would have immediately led you to discard the idea that the complexity is O(log n) or O(n log n).

---

Related Topics