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

i opinion on time , space complexity of algorithm implemented (in python) calculate complexity of algorithm print valid (i.e., opened , closed) combinations of n-pairs of parentheses (see all valid combinations of n-pair of parenthesis)

def find_par_n(n):     s = set(["()"])     in range(2, n + 1):         set_to_add = set()         str_ in s:             set_temp = set()             ana = set()             j in range(len(str_) + 1):                 str_c = str_[0:j] + '(' + str_[j:]                 if str_c in ana:                     continue                 ana.add(str_c)                 k in range(j + 1, len(str_) + 1):                     str_a = str_c                     str_a = str_a[0:k] + ')' + str_a[k:]                     set_temp.add(str_a)             set_to_add.update(set_temp)         s = set_to_add     return s 

most algorithm can improved in terms of time , space. please share thoughts.

let's try simpler version instead.

some theorems:

1. properly paired string of length. don't ask me prove one, please.
2. given paired string of length 2k, possible construct strings of length 2(k + 1) inserting pairs of parenthesis '()' @ every possible location within string. there 2k + 1 such positions.
3. to generate n pairs, need recursive insertion step n times (and strings of length 2n.

note not enough generate unique paired strings, because e.g. inserting () () yields same string twice (()()). upper bound 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:             in range(0, len(s)):                 add_parens(s[0:i] + '()' + s[i:], nparens)      n = 5       add_parens('', n)   

time complexity:

1. there 1 insertion point empty string.
2. there 3 insertion points (). ...

so in all:

t(n) = 1 * 3 * ... * 2n + 1 ~ o(n!) 

space complexity recursive version o(n(2n + 1)), i'm pretty sure possible bring down linear.