2800번: ZAGRADE

https://www.acmicpc.net/problem/2800


$O(ln2^n)$

stack으로 괄호쌍을 찾아준 다음, 비트마스크를 이용해 가능한 모든 문자열을 구하고 사전순 정렬한다.

#include<iostream>
#include<string>
#include<set>
using namespace std;
string s;
int cnt, stk[10], top;
pair<int, int> p[10];
set<string> st;
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') p[stk[top++] = cnt++].first = i;
        if (s[i] == ')') p[stk[--top]].second = i;
    }
    for (int i = 1 << cnt; --i;) {
        int ck[200] = {};
        for (int j = 0; j < cnt; j++) if (i & 1 << j) ck[p[j].first] = ck[p[j].second] = 1;
        string r;
        for (int j = 0; j < s.size(); j++) if (!ck[j]) r += s[j];
        st.insert(r);
    }
    for (auto it : st) cout << it << endl;
    return 0;
}