Generate Parentheses - LeetCode Solution in Java

1. Introduction

The "Generate Parentheses" problem involves creating all possible combinations of well-formed parentheses, which is a common problem to test understanding of recursion and backtracking in algorithms.

2. Problem

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

3. Solution Steps

1. Use recursion to solve the problem.

2. Maintain counts of open and close parentheses.

3. Add an open parenthesis if the open count is less than n.

4. Add a close parenthesis if the close count is less than the open count.

5. When the count of open and close parentheses equals n, a valid combination is formed.

4. Solution in Java

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

private void backtrack(List<String> result, String current, int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }

    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

Explanation:

1. backtrack is a recursive function that builds the parenthesis string.

2. It adds an "(" if the count of open parentheses (open) is less than max (n).

3. It adds a ")" if the count of close parentheses (close) is less than open.

4. When the length of current is equal to max * 2, a valid combination is formed, and it's added to result.

5. The function uses backtracking to explore all possible placements of ( and ) until all well-formed combinations are generated.