Problem
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
Solution: DFS
Time complexity: O(2^n)
Space complexity: O(k + n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Running time: 0 ms class Solution { public: vector<string> generateParenthesis(int n) { vector<string> ans; string cur; if (n > 0) dfs(n, n, cur, ans); return ans; } private: void dfs(int l, int r, string& s, vector<string>& ans) { if (l + r == 0) { ans.push_back(s); return; } if (r < l) return; if (l > 0) { dfs(l - 1, r, s += "(", ans); s.pop_back(); } if (r > 0) { dfs(l, r - 1, s += ")", ans); s.pop_back(); } } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment