fork(1) download
  1. S = input()
  2. N = len(S)
  3.  
  4. def go(last,o):
  5. # generate all *valid* suffixes for the current subsequence
  6. # assuming that S[last] was the last character used
  7. # and we currently have o opened parentheses
  8.  
  9. # if everything got closed, we can end right where we are
  10. if o==0: answer = 1
  11. else: answer = 0
  12.  
  13. # we can always try adding another '('
  14. nextl = last+1
  15. while nextl<N and S[nextl] != '(': nextl += 1
  16. if nextl<N: answer += go(nextl,o+1)
  17.  
  18. # only if o>0, we can also try adding another ')'
  19. if o>0:
  20. nextr = last+1
  21. while nextr<N and S[nextr] != ')': nextr += 1
  22. if nextr<N: answer += go(nextr,o-1)
  23.  
  24. # and that's it
  25. return answer
  26.  
  27. print(go(-1,0))
Success #stdin #stdout 0.09s 14068KB
stdin
()()
stdout
3