Generate Parentheses - Java Solution

1. Introduction

In this blog post, we tackle an intriguing problem that involves generating all possible combinations of well-formed parentheses. This problem is a classic example of recursive solution strategies and is often encountered in coding interviews.

Problem

Given n pairs of parentheses, the task is to write a function that generates all combinations of well-formed parentheses. A well-formed parentheses combination is one in which each opening parenthesis '(' has a corresponding closing parenthesis ')'.

2. Solution Steps

1. Use a recursive approach to build the combinations of parentheses.

2. At each recursive call, two choices are possible: add an opening parenthesis '(' or a closing parenthesis ')'.

3. Ensure that the number of opening parentheses does not exceed n and that the number of closing parentheses does not exceed the number of opening ones.

4. When the combination's length reaches 2 * n (n pairs), add it to the result list.

5. Return the list of valid combinations.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3)); // Test the function
    }

    // Function to generate all combinations of well-formed parentheses
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    // Helper function to build combinations recursively
    private static void backtrack(List<String> list, String str, int open, int close, int max) {
        if (str.length() == max * 2) {
            list.add(str);
            return;
        }

        if (open < max) {
            backtrack(list, str + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(list, str + ")", open, close + 1, max);
        }
    }
}

Output:

["((()))", "(()())", "(())()", "()(())", "()()()"]

Explanation:

1. generateParenthesis: This function kicks off the process of generating parentheses combinations.

2. It calls the backtrack function, which uses recursion to build valid combinations.

3. In backtrack, the function adds an opening parenthesis '(' if the number of opening ones is less than n, and a closing parenthesis ')' if the number of closing ones is less than the number of opening ones.

4. The function adds the string to the result list when its length reaches 2 * n, indicating a complete well-formed combination.

5. The final result is a list of all valid combinations of well-formed parentheses for the given number n.