Crack Leetcode 22: Generate Parentheses
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.
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:
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.
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.
- 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) ).
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!