Description

Given a n generate all "()" strings that are valid :: You can either add or close. While you are able recursively do both.

Runtime

O(n)

Pseudocode

res = []

def generate(string, open_count):
	if len(string) == n*2:
		if open_count == 0:
			res.append(string)
		return
	
	if you can still add one:
		generate(string+open, open_count++)
	if you can close one:
		generate(string+close, open_count--)

generate("", 0)
return res