Problem: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1 Output: ["()"]
Approach: The first direct approach would be generate all the 2^2n combinations and add the valid combinations to the result. We can easily generate all the valid combinations using backtracking.
We can make the above approach a little better, instead of adding '(' and ')' blindly, we can add them when we know it will remain a valid sequence. We can maintain count of open and close braces to achieve it. We know that we can have at max 'n' open and close braces so we add '(' if its count is less than or equal to 'n' and we add ')' only if its count is less than or equal to count of open braces.
That's all!
Implementation in C#:
Approach 1:
public IList<string> GenerateParenthesis(int n)
{
List<string> result = new List<string>();
char[] curr = new char[2 * n];
this.GenerateParenthesis(curr, 0, result);
return result;
}
private void GenerateParenthesis(char[] curr, int currPos, List<string> result)
{
if (currPos == curr.Length)
{
if (this.IsValid(curr))
{
result.Add(new string(curr));
}
return;
}
curr[currPos] = '(';
this.GenerateParenthesis(curr, currPos + 1, result);
curr[currPos] = ')';
this.GenerateParenthesis(curr, currPos + 1, result);
}
private bool IsValid(char[] curr)
{
int count = 0;
foreach(char ch in curr)
{
if (ch == '(')
{
++count;
}
else
{
--count;
}
if (count < 0)
{
return false;
}
}
return count == 0;
}
Approach 2:
public IList<string> GenerateParenthesis(int n)
{
List<string> result = new List<string>();
char[] curr = new char[2 * n];
this.GenerateParenthesis(curr, 0, result, n, 0, 0);
return result;
}
private void GenerateParenthesis(char[] curr, int currPos, List<string> result, int limit, int open, int close)
{
if (currPos == curr.Length)
{
result.Add(new string(curr));
return;
}
if (open < limit)
{
curr[currPos] = '(';
this.GenerateParenthesis(curr, currPos + 1, result, limit, open + 1, close);
}
if(close < open)
{
curr[currPos] = ')';
this.GenerateParenthesis(curr, currPos + 1, result, limit, open, close + 1);
}
}
Complexity: Approach 1: O(2^2n * n) Validation of 2^2n combinations of length n
Approach 2: O( 4^n / sqrt(n)) nth catalan number * n = (4 ^ n / (n * sqrt(n)) * n
No comments:
Post a Comment