NeetCode 150: Generate Parentheses

Open Table of contents

The Problem
The Approach
My Solution

The Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1	Example 2
Input: `n` = 3 Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()“]	Input: `n` = 1 Output: [”()“]

The Approach

Initially, I was stumped.

After doing some reading, I realised that the ideal approach is to use backtracking along with recursion to determine all valid cases.

My Solution

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        backtrackingAllPossiblePaths(result, n, 0, 0, "");
        return result;
    }
    
    // Uses backtracking (along with recursion to determine all valid cases).
    private void backtrackingAllPossiblePaths(List<String> result, int n, int openTotalBrackets, int closeTotalBrackets, String currentCombination) {
        // Base case: When the combination length is == to max possible size. This combination is then added to result.
        if (currentCombination.length() == (n * 2)) {
            result.add(currentCombination);
            return;
        }
        // NOTE: The below are not separate cases, but separate checkers!

        // Adds a new "(" to the combination.
        if (openTotalBrackets < n) {
            backtrackingAllPossiblePaths(result, n, openTotalBrackets + 1, closeTotalBrackets, currentCombination + "(");
        }

        // Adds a new ")" to the combination.
        if (closeTotalBrackets < openTotalBrackets) {
            backtrackingAllPossiblePaths(result, n, openTotalBrackets, closeTotalBrackets + 1, currentCombination + ")");
        }
    }
}

We first initialize result which is an ArrayList to keep track of all valid combinations.

backtrackingAllPossiblePaths() keeps track of the openTotalBrackets, closeTotalBrackets which determine String currentCombination. It has a base case, (currentCombination.length() == (n * 2)) which adds this combination to result when its length is the twice of n (due to pairs).

Each call of backtrackingAllPossiblePaths() checks:

openTotalBrackets < n: Add an open bracket to currentCombination.
closeTotalBrackets < openTotalBrackets: Add an close bracket to currentCombination if there are more open brackets than close brackets.

You can visualize each call of backtrackingAllPossiblePaths() as a node in a Tree-like structure, where each checker’s outcome branches off into a new node (adding a bracket to currentCombination). It repeats this until the base case is achieved (i.e. the leaf).