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:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
(Photo taken from Leetcode:

Back Tracking Solution:

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:

Image for post
Image for post

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.

Image for post
Image for post


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:

Image for post
Image for post

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

Complexity 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.

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!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store