source: https://leetcode.com/problems/generate-parentheses/
C/C++ Solution to LeetCode problem 22. Generate Parentheses.
Problem
Given n
pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Examples
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints
1 <= n <= 8
Solution
- We will use Dynamic Programing.
- We know that we need
n
open parentheses'()'
andn
close parentheses')'
. - There cannot be (at any time) less
'('
than')'
in our current solution. - The method will count how many
'('
and')'
are still availabe to add to the current solution. - Once there are
0
'('
than')'
left, we add that solution to the final result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
vector<string> result;
void generate(string s, int o, int c) {
if (o == 0 && c == 0)
result.push_back(s);
if (o)
generate(s + "(", o - 1, c);
if (o<c)
generate(s + ")", o, c - 1);
}
public:
vector<string> generateParenthesis(int n) {
generate("", n, n);
return result;
}
};