Intermediate Level
Implement the generateParenthesesCountImportant method that counts valid parentheses combinations for n pairs.
The input is an integer n, representing the number of pairs of parentheses.
Your task is to count how many valid parentheses strings can be formed using exactly n opening brackets and n closing brackets.
A parentheses string is valid when every closing bracket has a matching opening bracket before it. For example, when n = 3, there are 5 valid strings.
Example 1
Input
n (int) =
3Returns (int)
5Example 2
Input
n (int) =
1Returns (int)
1Example 3
Input
n (int) =
2Returns (int)
2Use backtracking to build only valid strings.
At any step, you may add an opening bracket if the number of opening brackets used is still less than n. You may add a closing bracket only when there are more opening brackets than closing brackets already used.
Whenever the string length becomes 2 * n, one valid combination has been formed, so increase the count.
Pseudocode:
function generateParenthesesCountImportant(n):
count = 0
backtrack(openUsed, closeUsed):
if openUsed == n and closeUsed == n:
count++
return
if openUsed < n:
backtrack(openUsed + 1, closeUsed)
if closeUsed < openUsed:
backtrack(openUsed, closeUsed + 1)
backtrack(0, 0)
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run