#include <stdio.h>
#include <stdlib.h>
/*
Generate all valid parentheses combinations for a given n.
Approach:
---------
We use a backtracking strategy:
- We may add '(' if we still have some left.
- We may add ')' only if it keeps the string valid:
meaning we already placed more '(' than ')'.
This ensures we never build invalid partial strings,
which avoids wasted work and keeps the algorithm efficient.
Memory:
-------
We allocate a buffer of size 2*n + 1 for each candidate string.
The result is printed directly instead of stored, keeping the
program simple and avoiding dynamic arrays.
*/
// Recursive helper that builds valid parentheses strings.
void build_parentheses(
int openRemaining, // how many '(' we can still add
int closeRemaining, // how many ')' we can still add
char *buffer, // current partial string
int index // current write position in buffer
) {
// When both counters reach zero, we have a complete valid string.
if (openRemaining == 0 && closeRemaining == 0) {
buffer[index] = '\0';
printf("%s\n", buffer);
return;
}
// If we can still place an opening parenthesis, do so.
if (openRemaining > 0) {
buffer[index] = '(';
build_parentheses(openRemaining - 1, closeRemaining, buffer, index + 1);
}
// We can place a closing parenthesis only if it keeps the string valid.
// That means we must have placed more '(' than ')' so far.
if (closeRemaining > openRemaining) {
buffer[index] = ')';
build_parentheses(openRemaining, closeRemaining - 1, buffer, index + 1);
}
}
// Wrapper that prepares the buffer and starts the recursion.
void generateParentheses(int n) {
// Allocate enough space for the longest string: 2*n chars + null terminator.
char *buffer = malloc((2 * n + 1) * sizeof(char));
if (!buffer) {
fprintf(stderr, "Memory allocation failed\n");
return;
}
build_parentheses(n, n, buffer, 0);
free(buffer);
}
int main(void) {
int n = 3; // You can change this to any positive integer.
printf("Valid parentheses combinations for n = %d:\n", n);
generateParentheses(n);
return 0;
}
/*
run:
Valid parentheses combinations for n = 3:
((()))
(()())
(())()
()(())
()()()
*/
