This program generates all valid combinations of n pairs of parentheses using recursion. The approach leverages backtracking to ensure that only valid parentheses combinations are generated.

Go Program Code:

package main

import (
    "fmt"
)

// generateParentheses is a recursive function that generates valid parentheses combinations
// n is the total number of pairs of parentheses
// left and right track the number of left and right parentheses placed so far
// current is the current combination being built
// result stores all valid combinations generated
func generateParentheses(n int, left int, right int, current string, result *[]string) {
    // If the current combination has n pairs of parentheses, add it to the result
    if len(current) == 2*n {
        *result = append(*result, current)
        return
    }

    // If we can add more left parentheses, do so
    if left < n {
        generateParentheses(n, left+1, right, current+"(", result)
    }

    // If we can add more right parentheses, do so (only if it balances the left)
    if right < left {
        generateParentheses(n, left, right+1, current+")", result)
    }
}

// generateValidParentheses initializes the process for generating valid combinations
func generateValidParentheses(n int) []string {
    result := []string{}
    generateParentheses(n, 0, 0, "", &result)
    return result
}

func main() {
    // Example usage: generate combinations for 3 pairs of parentheses
    n := 3
    result := generateValidParentheses(n)

    fmt.Println("Valid combinations of", n, "pairs of parentheses:")
    for _, combination := range result {
        fmt.Println(combination)
    }
}

Explanation of the Program Structure:

1. Imports: The program imports the “fmt” package for printing the output.
2. generateParentheses Function:This is the main recursive function that generates valid combinations of parentheses. It takes the following parameters:
   • n: the number of pairs of parentheses.
   • left: the number of left parentheses placed so far.
   • right: the number of right parentheses placed so far.
   • current: the current string representing the combination being built.
   • result: a pointer to a slice that stores all valid combinations.

   The base case occurs when the length of the current string is equal to 2 * n, meaning the combination has been fully formed. At that point, the combination is added to the result slice. The function uses two conditions to ensure the parentheses remain valid:

   • If the number of left parentheses placed so far is less than n, a new left parenthesis can be added.
   • If the number of right parentheses placed so far is less than the number of left parentheses, a new right parenthesis can be added.
3. generateValidParentheses Function:This function acts as a wrapper around the recursive generateParentheses function. It initializes the result slice and starts the recursive process with 0 left and right parentheses.
4. main Function:The main function demonstrates how to use the generateValidParentheses function. It generates valid combinations for a given number of parentheses (e.g., 3 in this case) and prints each valid combination to the console.

Output:

For n = 3, the program will output the following valid combinations of parentheses:

Valid combinations of 3 pairs of parentheses:
((()))
(()())
(())()
()(())
()()()

Time Complexity:

The time complexity of this algorithm is O(4^n / sqrt(n)) which corresponds to the Catalan number C_n</>, representing the number of valid combinations of parentheses.

Key Points to Note:

1. Recursion & Backtracking:
   The core idea is using recursion to build up valid parentheses combinations. The program ensures valid combinations by only allowing the addition of a right parenthesis when it “matches” a previous left parenthesis, thus maintaining validity.
2. Catalan Numbers:
   The number of valid combinations of n pairs of parentheses corresponds to the nth Catalan number. These numbers grow exponentially, which is why the time complexity of this solution is about O(4^n / sqrt(n)).
3. Printing the Result:
   After generating all the valid combinations, the program prints them in a straightforward manner.

This program should be helpful for understanding the algorithm and seeing it implemented in Go.