括弧のパターン生成

/

括弧のパターン生成について

タグ

概要

  • 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);
}

参考