Recursion Backtracking Combinatorics
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) = 3
Return:
(int) 5
Example 2
Input:
n (int) = 1
Return:
(int) 1
Example 3
Input:
n (int) = 2
Return:
(int) 2

Use 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 count
Run your code to see the result.