括弧のパターン生成について
概要
- dfsを利用したバックトラック法
設定
- n=3の時、
["((()))","(()())","(())()","()(())","()()()"]を生成する - 括弧の対応が成立しなければならない
ソリューション
class Solution {
public:
vector<string> generateParenthesis(int n);
};
void dfs(int lnum, int rnum, int n, string gen, vector<string>& lst) {
if(lnum < rnum) return;
if( lnum == n and rnum == n){
lst.push_back(gen);
}
if(lnum +1 <= n) dfs(lnum+1, rnum, n, gen+"(", lst);
if(rnum +1 <= n) dfs(lnum, rnum+1, n, gen+")", lst);
}
vector<string> Solution::generateParenthesis(int n) {
vector<string> lst;
dfs(0, 0, n, "", lst);
return lst;
}
int main() {
auto s = Solution();
auto lst = s.generateParenthesis(3);
print_it(lst);
}