> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/05-03-2022.md).

# 05/03/2022

Method: use backtracking

At each point of constructing the string of length 2n we make a choice.

We can place a "(" and recurse or we can place a ")" and recurse.

But we can't just do that placement, we need 2 critical pieces of information.

The number of left parens left to place. The number of right parens left to place.

We have 2 critical rules at each placement step.

We can place a left parentheses if the number of the left is less than number n.

We can only place a right parentheses if the number of the right is less than the number of left.

Once we establish these constraints on our branching we know that when we have 0 left of both parens to place that we are done, we have an answer in our base case.

Time O(4^n/n^1/2)

Space O(N)

Our Choice: Whether we place a left or right paren at a certain decision point in our recursion.

Our Constraints: We can't place a right paren unless we have left parens to match against.

Our Goal: Place all k left and all k right parens.

The Key