#22 Generate Parentheses - Solution

The Generate Parentheses problem asks you to generate all combinations of well‑formed parentheses for a given n. The most common strategy is backtracking, where you build the string step by step while ensuring it always remains valid.

The key idea is to track how many opening and closing brackets have been used so far. You can add an opening parenthesis if the number of openings used is less than n. A closing parenthesis can only be added if it will not break validity—meaning the number of closing brackets used must always be less than the number of openings.

This pruning ensures that invalid states are never explored, making the recursion efficient. Another conceptual way to view the problem is through Catalan numbers, which describe the total number of valid combinations.

The overall time complexity grows with the number of valid combinations generated, while space complexity mainly comes from the recursion stack and storing results.

Approach	Time Complexity	Space Complexity
Backtracking (Recursive generation)	O(4^n / √n)	O(n)
Dynamic Programming / Catalan-based construction	O(4^n / √n)	O(n)

Solutions (6)

Backtracking Approach

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.

C C++Java Python C#JavaScript

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}

Explanation

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.