Micro-Drill #136 — Generate parentheses backtrack

Recursion & DP Target: 15s

Track open/close counts. Only add close paren when close < open.

def bt(o, c, cur):
    if len(cur) == 2*n: res.append(cur); return
    if o &lt; n: bt(o+1, c, cur+'(')
    if c &lt; o: bt(o, c+1, cur+')')

Type it from memory. Go.