The trick here is to name the state correctly, then let the implementation follow. For 22. Generate Parentheses, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, backtracking.
The notes already sitting in the source point us in the right direction:
- backtrack
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backtrack, generateParenthesis, valid, generateAll.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(2^(2n)*n), space: O(2^(2n)*n)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtrack
02//Runtime: 4 ms, faster than 89.87% of C++ online submissions for Generate Parentheses.
03//Memory Usage: 7 MB, less than 100.00% of C++ online submissions for Generate Parentheses.
04class Solution {
05public:
06 vector<char> pars = {'(', ')'};
07
08 void backtrack(int& n, string& comb, vector<string>& combs){
09 int open = count(comb.begin(), comb.end(), '(');
10 int close = comb.size() - open;
11
12 //short for open == n && close == n
13 if(close == n){
14 combs.push_back(comb);
15 }
16
17 for(int i = 0; i < pars.size(); i++){
18 //only when open par's count < n, we can append open par
19 //only when close par's count < open par's count, we can append close par
20 if((i == 0 && open < n) || (i == 1 && open > close)){
21 comb += pars[i];
22 backtrack(n, comb, combs);
23 comb.pop_back();
24 }
25 }
26 };
27
28 vector<string> generateParenthesis(int n) {
29 string comb;
30 vector<string> combs;
31 backtrack(n, comb, combs);
32 return combs;
33 }
34};
35
36//Approach 1: Brute Force, recursion
37//Runtime: 20 ms, faster than 11.14% of C++ online submissions for Generate Parentheses.
38//Memory Usage: 6.9 MB, less than 100.00% of C++ online submissions for Generate Parentheses.
39//time: O(2^(2n)*n), space: O(2^(2n)*n)
40class Solution {
41public:
42 bool valid(string& comb){
43 int balance = 0;
44 for(char c : comb){
45 if(c == '(') balance++;
46 else balance--;
47 if(balance < 0) return false;
48 }
49 return (balance == 0);
50 }
51
52 void generateAll(string& comb, vector<string>& combs, int n){
53 if(comb.size() == 2*n){
54 // cout << comb << endl;
55 if(valid(comb))combs.push_back(comb);
56 return;
57 }
58
59 for(char c : {'(', ')'}){
60 comb.push_back(c);
61 generateAll(comb, combs, n);
62 comb.pop_back();
63 }
64 }
65
66 vector<string> generateParenthesis(int n) {
67 string comb;
68 vector<string> combs;
69 generateAll(comb, combs, n);
70 return combs;
71 }
72};
73
74//Approach 1: Brute Force, recursion
75//Runtime: 16 ms, faster than 15.92% of C++ online submissions for Generate Parentheses.
76//Memory Usage: 12.4 MB, less than 92.56% of C++ online submissions for Generate Parentheses.
77/*
78time: O(2^(2n)*n), space: O(2^(2n)*n)
79we may choose either ( or ) for a comb of size 2*n,
80so there are total 2^(2n) possibilities.
81And for each possibility, we need to spend O(n) time to check for its validity.
82*/
83class Solution {
84public:
85 vector<string> generateParenthesis(int n) {
86 if(n == 0) return {""};
87
88 vector<string> ans;
89
90 for(int c = 0; c < n; c++){
91 vector<string> lefts = generateParenthesis(c);
92 vector<string> rights = generateParenthesis(n-1-c);
93 for(string& left : lefts){
94 for(string& right : rights){
95 ans.push_back("(" + left + ")" + right);
96 }
97 }
98 }
99
100 return ans;
101 }
102};
103
104//backtrack
105//Runtime: 4 ms, faster than 89.84% of C++ online submissions for Generate Parentheses.
106//Memory Usage: 11.6 MB, less than 92.56% of C++ online submissions for Generate Parentheses.
107//time: O(4^n/sqrt(n)), space: O(4^n/sqrt(n))
108class Solution {
109public:
110 void backtrack(string& comb, vector<string>& combs, int open, int close, int n){
111 if(comb.size() == n*2){
112 combs.push_back(comb);
113 return;
114 }
115
116 if(open < n){
117 comb += '(';
118 backtrack(comb, combs, open+1, close, n);
119 comb.pop_back();
120 }
121
122 if(close < open){
123 comb += ')';
124 backtrack(comb, combs, open, close+1, n);
125 comb.pop_back();
126 }
127 }
128
129 vector<string> generateParenthesis(int n) {
130 string comb = "";
131 vector<string> combs;
132 backtrack(comb, combs, 0, 0, n);
133 return combs;
134 }
135};
136
137//Approach 3: Closure Number
138//Runtime: 20 ms, faster than 11.14% of C++ online submissions for Generate Parentheses.
139//Memory Usage: 13.3 MB, less than 90.08% of C++ online submissions for Generate Parentheses.
140//time: O(4^n/sqrt(n))
141class Solution {
142public:
143 vector<string> generateParenthesis(int n) {
144 if(n == 0) return {""};
145 vector<string> ans;
146 for(int c = 0; c < n; c++){
147 for(string left : generateParenthesis(c)){
148 for(string right : generateParenthesis(n-1-c)){
149 ans.push_back("(" + left + ")" + right);
150 }
151 }
152 }
153
154 return ans;
155 }
156};Cost
Complexity
Time
O(2^(2n)*n), space: O(2^(2n)*n)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.