题目介绍
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
1 | [ |
2 | "((()))", |
3 | "(()())", |
4 | "(())()", |
5 | "()(())", |
6 | "()()()" |
7 | ] |
解
1 | class Solution { |
2 | private: |
3 | void help (vector<string>& ret, string tmp, int left, int right) { |
4 | if (left > right) { |
5 | return; |
6 | } |
7 | if (right == 0) { |
8 | ret.emplace_back(tmp); |
9 | return; |
10 | } |
11 | if (left > 0) { |
12 | help(ret, tmp+"(", left-1, right); |
13 | } |
14 | help(ret, tmp+")", left, right-1); |
15 | } |
16 | public: |
17 | vector<string> generateParenthesis(int n) { |
18 | vector<string> ret; |
19 | if (n < 1) { |
20 | return ret; |
21 | } |
22 | help(ret, "", n, n); |
23 | return ret; |
24 | } |
25 | }; |
Runtime: 8 ms
Memory Usage: 17.3 MB
