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.
Comments
Post a Comment