題目連結: https://zerojudge.tw/ShowProblem?problemid=a229
# 內容
請寫一個程式把所有合法括號匹配方式列出來！
Ex. (()) , ((()())) , ()((())) 是合法的匹配方式
)(, (()))( , ()(()( 是不合法的匹配方式
合法匹配的括號，從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧！
# 解題思路
使用 DFS，如果途中 (>) 則直接 return，直到放置數達到 n*2 為止
# 程式碼
#include <iostream> | |
using namespace std; | |
string s; int a, b; | |
void dfs(int n) { | |
if(a < b) return; | |
if(s.size() == n * 2) { if(a == b) cout << s << '\n'; } | |
else { | |
s.push_back('('); a ++; dfs(n); s.pop_back(); a--; | |
s.push_back(')'); b ++; dfs(n); s.pop_back(); b--; | |
} | |
} | |
main() { | |
int n; while(cin >> n) dfs(n); | |
} |
