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 <iostream>
2#include <vector>
3using namespace std;
4
5void backtrack(string current, int open, int close, int max, vector<string> &result) {
6 if (current.length() == max * 2) {
7 result.push_back(current);
8 return;
9 }
10 if (open < max) {
11 backtrack(current + "(", open + 1, close, max, result);
12 }
13 if (close < open) {
14 backtrack(current + ")", open, close + 1, max, result);
15 }
16}
17
18vector<string> generateParenthesis(int n) {
19 vector<string> result;
20 backtrack("", 0, 0, n, result);
21 return result;
22}
23
24int main() {
25 vector<string> parentheses = generateParenthesis(3);
26 for (const string &s : parentheses) {
27 cout << s << endl;
28 }
29 return 0;
30}This C++ code uses a recursive function with backtracking to generate well-formed parentheses for a given n. We append either '(' or ')' to our current string based on the remaining number of each we can use by ensuring ')' never exceeds '('. Once the length of the current string equals 2 * n, it's added to the results. This uses a depth-first search approach to explore all possible combinations while pruning invalid ones at each decision point.