22. Generate Parentheses

Intitution

To generate all valid combinations of n pairs of parentheses, we can use backtracking. A valid parentheses combination must always have:

• An equal number of opening '(' and closing ')' parentheses.

• At no point in the combination can the number of closing brackets exceed the number of opening ones.

We build the string character by character, ensuring that we only add an opening bracket '(' when we still have quota left, and a closing bracket ')' only if it balances out a previous '('.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(2^N)$

Code

List<String> validParenthesesCombinations = new ArrayList<>();

public void buildParenthesisCombinations(int remainingPairs, int openCount, char[] currentCombination, int currentIndex) {
    // Base case: All positions filled
    if (remainingPairs == 0) {
        StringBuilder combination = new StringBuilder();
        for (char ch : currentCombination) {
            combination.append(ch);
        }
        validParenthesesCombinations.add(combination.toString());
        return;
    }

    // Option 1: Add a closing bracket if there's an unmatched opening
    if (openCount > 0) {
        currentCombination[currentIndex] = ')';
        buildParenthesisCombinations(remainingPairs - 1, openCount - 1, currentCombination, currentIndex + 1);
    }

    // Option 2: Add an opening bracket if we can still open more
    if (openCount < remainingPairs) {
        currentCombination[currentIndex] = '(';
        buildParenthesisCombinations(remainingPairs, openCount + 1, currentCombination, currentIndex + 1);
    }
}

public List<String> generateParenthesis(int n) {
    buildParenthesisCombinations(n * 2, 0, new char[n * 2], 0);
    return validParenthesesCombinations;
}