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:

(Photo taken from Leetcode: https://leetcode.com/problems/generate-parentheses/)

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!