Generate Parentheses - C Solution

1. Introduction

This blog post delves into an interesting C programming problem: generating all combinations of well-formed parentheses. The challenge is a classic example of using backtracking to generate permutations or combinations, widely applicable in areas like compiler design, mathematical expressions, and algorithm design.

Problem

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

2. Solution Steps

1. Use a recursive approach to build the combinations.

2. At each stage, add either an opening or closing parenthesis, maintaining the balance.

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

4. When the current string reaches the length of 2 * n, add it to the result list.

3. Code Program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to recursively generate well-formed parentheses combinations
void generateParenthesisRecursive(int n, int open, int close, char *current, int pos, char **result, int *returnSize) {
    if (close == n) { // Check if the combination is complete
        current[pos] = '\0'; // Null-terminate the current combination
        result[*returnSize] = strdup(current); // Add the combination to the result
        (*returnSize)++; // Increment the number of combinations found
        return;
    }

    if (open < n) { // If we can add an opening parenthesis
        current[pos] = '('; // Add an opening parenthesis
        generateParenthesisRecursive(n, open + 1, close, current, pos + 1, result, returnSize); // Recurse with added '('
    }

    if (close < open) { // If we can add a closing parenthesis
        current[pos] = ')'; // Add a closing parenthesis
        generateParenthesisRecursive(n, open, close + 1, current, pos + 1, result, returnSize); // Recurse with added ')'
    }
}

// Function to generate all combinations of well-formed parentheses
char **generateParenthesis(int n, int *returnSize) {
    *returnSize = 0;
    int maxSize = 1;
    for (int i = 0; i < n; ++i) { // Calculate maximum possible combinations
        maxSize *= 2;
    }

    char **result = malloc(maxSize * sizeof(char *)); // Allocate memory for storing the combinations
    char *current = malloc(2 * n + 1); // Current combination

    generateParenthesisRecursive(n, 0, 0, current, 0, result, returnSize); // Start recursion

    free(current); // Free the current combination's memory
    return result;
}

int main() {
    int n = 3; // Number of pairs of parentheses
    int returnSize;
    char **combinations = generateParenthesis(n, &returnSize); // Generate parentheses combinations

    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", combinations[i]); // Print each combination
        free(combinations[i]); // Free memory allocated for the combination
    }
    free(combinations); // Free the array of combinations
    return 0;
}

Output:

((()))
(()())
(())()
()(())
()()()

Explanation:

The program uses a recursive function to build well-formed parentheses combinations. At each recursive call, it decides whether to add an opening or closing parenthesis, ensuring the balance is maintained. Once a valid combination of 2 * n length is formed, it's added to the result list. 

The main function demonstrates this with 'n' equal to 3, generating all possible well-formed combinations like '(()())', '()(())', etc. 

This approach efficiently explores all valid permutations using the backtracking paradigm.