# Crack Leetcode 22: Generate Parentheses

## There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 22 — Generate Parentheses— together. After this article, you’ll have a better understanding of Back Tracking. Without further ado, let’s get started.

# Problem Description:

# Back Tracking Solution:

## Ideation:

The idea is to have a empty string, and put “(” and “)” in one by one.

We put “(” in first. In total there are n “(”. We can keep adding “(” in until we used up all the “(”.

Then we start adding “)” in. To keep the resulting string well-formed, we only add in “)” when the number of existing “(” exceeds the number of “)” in the current string:

When current string length == 2*n, we got an answer. Therefore we record it, and return to previous step to search for other possible combinations.

## Python Code:

.

## Code Analysis: Back Tracking Tree

At first sight, it looks complicated to get a clear view of how it backtracks, specifically where the “return” returns to. At least I struggled for a while.

I didn’t give up. In the end, I successfully get this tree, which clearly shows how the program goes. It turned out, back tracking is just DFS, or in my opinion, traverse a tree:

Note that the tree is not full, because our two if-cases cut some of the tree branches.

**Complexity Analysis:**

## My Analysis:

**Time Complexity:**The tree has a max height of 2n, therefore the max nodes the tree has is 2^ 2n. Therefore the time complexity is O(2^ 2n)=**O(4^n)**.**Space Complexity:**We have 2^(2n-1) leaves at most, therefore, the time complexity is**O(4^n)**.

Clearly, my analysis over estimated the total tree nodes, and the number of leaves.

## Leetcode Analysis:

The tree is not full, and the number of leaves actually can be described by n-th* Catalan number*, which is bounded by 4^n /(n ^ 3/2).

**Time Complexity:**since each sequence at most back tracks 2n steps, time complexity is n-th*Catalan number**2n, which gives**O( 4^n / (n^ 1/2) )**.**Space Complexity:**since each sequence takes at most 2*n space, the answer list takes at most n-th*Catalan number**2n space, which gives**O( 4^n / (n^ 1/2) )**.

# The End:

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!