Well, there are two ways to add a open or close parenthesis to the current string.
- If number of
(is less thann, you can add(; - If number of
)is less than number of(, you can add).
Maintain a res for all the possible parenthesis and a temporary string sol for the current answer. Now we have the following code.
1 class Solution { 2 public: 3 vector<string> generateParenthesis(int n) { 4 vector<string> res; 5 string sol; 6 genParen(sol, 0, 0, n, res); 7 return res; 8 } 9 private: 10 void genParen(string& sol, int open, int close, int total, vector<string>& res) { 11 if (open == total && close == total) { 12 res.push_back(sol); 13 return; 14 } 15 if (open < total) { 16 sol += '('; 17 genParen(sol, open + 1, close, total, res); 18 sol.resize(sol.length() - 1); 19 } 20 if (close < open) { 21 sol += ')'; 22 genParen(sol, open, close + 1, total, res); 23 sol.resize(sol.length() - 1); 24 } 25 } 26 };
