https://leetcode.com/problems/generate-parentheses/
Imagine we already have the all the well formed parentheses in 0 pairs to n-1 pairs. We can get the n pairs of parentheses by combining the x pairs with n-1-x pairs then combine with one pair “()”.
Why we have to separately consider the single brackets is because we can not just combine the x pairs and n-x pairs to make new well-formed parentheses. We may miss some situations.
We may not think of the well-formed n-1 pairs combine with one pair, but one pair combine with the n-1 pairs.
We can easily see that there is only three place to insert the n-1 pairs.
_1_(_2_)_3_
the first and third place are duplicate, we can just select the third place.
now what we do is to put our x pairs an n-x-1 pairs in to the blanks.
At first, 0 pair and 1 pair parentheses has only one combination: {""}, {"()"}
, with this, we can get the 2 pairs parentheses and then all the way to n pairs.
1 | class Solution { |