Generate all valid parenthesis of length k

'''
The time complexity looks like 2^n as there are two options either select open or close, but actually it is not because you can't add close before open so some pruning happened and it brought the number to catalan number(total number of valid parenthesis of n size) and n for each string to build so Catalan number*N is the time compleixty.
explore catalan number proof in more detail.
'''

#M-1 for better time complexity
def fun(cur, open_cnt, close_cnt, n, ans):
    if open_cnt == close_cnt == n:
        ans.append(cur)
        return

    if open_cnt < n:
        fun(cur + '(', open_cnt + 1, close_cnt, n, ans)

    if close_cnt < open_cnt:
        fun(cur + ')', open_cnt, close_cnt + 1, n, ans)