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: https://leetcode.com/problems/generate-parentheses/)

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