Sponsored
Sponsored
The key idea here is to build the solution by choosing either an opening or a closing parenthesis at each step. We make sure that any partial solution is valid - at any point in time, the number of closing parentheses cannot exceed the number of opening ones. We also stop adding parentheses when we have used 'n' of each.
Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth.
Space Complexity: O(n) for recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void generate(char *current, int open, int close, int max, char ***result, int *size) {
6 if (strlen(current) == max * 2) {
7 (*result)[*size] = strdup(current);
8 (*size)++;
9 return;
10 }
11 if (open < max) {
12 strcat(current, "(");
13 generate(current, open + 1, close, max, result, size);
14 current[strlen(current) - 1] = '\0';
15 }
16 if (close < open) {
17 strcat(current, ")");
18 generate(current, open, close + 1, max, result, size);
19 current[strlen(current) - 1] = '\0';
20 }
21}
22
23char **generateParenthesis(int n, int *returnSize) {
24 char **result = (char **)malloc(sizeof(char *) * 1000);
25 *returnSize = 0;
26 char current[2 * n + 1];
27 current[0] = '\0';
28 generate(current, 0, 0, n, &result, returnSize);
29 return result;
30}
31
32int main() {
33 int size;
34 char **parentheses = generateParenthesis(3, &size);
35 for (int i = 0; i < size; i++) {
36 printf("%s\n", parentheses[i]);
37 free(parentheses[i]);
38 }
39 free(parentheses);
40 return 0;
41}This solution uses backtracking to generate all valid combinations of parentheses. Start with an empty string, and use two counters: 'open' and 'close'. As long as 'open' is less than 'n', add an opening parenthesis. As long as 'close' is less than 'open', add a closing parenthesis. When the length of the current string is 2 * n, it's added to the result. Each combination is built step-by-step, exploring possibilities and backtracking if needed.