Java Program

public class GenerateParentheses {
    
    /**
     * Generates all valid combinations of n pairs of parentheses.
     * 
     * @param n The number of pairs of parentheses.
     * @return A list containing all valid combinations.
     */
    public List generateParenthesis(int n) {
        List result = new ArrayList<>();
        generate(result, "", 0, 0, n);
        return result;
    }

    /**
     * Helper method to generate parentheses combinations using backtracking.
     * 
     * @param result The list to store valid combinations.
     * @param current The current string being built.
     * @param open The count of open parentheses used.
     * @param close The count of close parentheses used.
     * @param max The total number of pairs.
     */
    private void generate(List result, String current, int open, int close, int max) {
        // If the current string has reached the maximum length, add it to results
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }

        // If we can add an open parenthesis, do so
        if (open < max) {
            generate(result, current + "(", open + 1, close, max);
        }

        // If we can add a close parenthesis, do so
        if (close < open) {
            generate(result, current + ")", open, close + 1, max);
        }
    }

    public static void main(String[] args) {
        GenerateParentheses gp = new GenerateParentheses();
        int n = 3; // Example: 3 pairs of parentheses
        List combinations = gp.generateParenthesis(n);
        System.out.println(combinations);
    }
}

Program Structure Explanation

The program consists of a class named GenerateParentheses that includes methods for generating valid parentheses combinations.

• generateParenthesis(int n): This public method initializes the result list and calls the helper method generate.
• generate(List result, String current, int open, int close, int max): This private helper method uses backtracking to construct valid combinations. It keeps track of the number of open and close parentheses and builds the current string recursively.
• main(String[] args): The main method serves as an entry point to the program, where it creates an instance of GenerateParentheses, defines the number of pairs, and prints the valid combinations.

How the Program Works

The program uses a recursive backtracking approach to explore all possible combinations of parentheses. It ensures that at any point:

• The number of open parentheses does not exceed n</>.
• The number of close parentheses does not exceed the number of open parentheses.

This guarantees that only valid combinations are formed, avoiding scenarios such as unmatched closing parentheses.

Example Output

If you run the program with n = 3, the output will be:

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