22. Generate Parentheses - medium
문제
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
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
제한사항
입출력 예
풀이
- Back Tracking
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
class Solution {
public:
// Back Tracking
void OpenClose(vector<string>& ans, int n, string str, int open, int close){
// '(', ')' 괄호가 2개가 한세트 이므로 2*n이 정답의 총 길이
if(str.size() == 2 * n){
ans.push_back(str);
return;
}
// '(' 가 n개수보다 작으면 '(' 추가
if(open < n)
OpenClose(ans, n, str+'(', open+1, close);
// ')' 가 현재 문자의 '(' 개수 보다 작으면 ')' 추가
if(close < open)
OpenClose(ans, n, str+')', open, close+1);
}
vector<string> generateParenthesis(int n) {
vector<string> answer;
OpenClose(answer, n, "",0 ,0);
return answer;
}
};