原題目在zerojudge,若對於backtracking技術不熟可看演算法筆記-backtracking
Problem
請寫一個程式把所有合法括號匹配方式列出來!
Ex:
- 以下是合法的匹配方式
(())((()()))()((()))
- 以下是不合法的匹配方式
)((()))(()(()(
合法匹配的括號 ， 從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧!
Ex. 合法匹配 ((()()))
字串 ( 左括弧 : 1 >= 右括弧 : 0
字串 (( 左括弧 : 2 >= 右括弧 : 0
字串 ((( 左括弧 : 3 >= 右括弧 : 0
字串 ((() 左括弧 : 3 >= 右括弧 : 1
字串 ((()( 左括弧 : 4 >= 右括弧 : 1
字串 ((()() 左括弧 : 4 >= 右括弧 : 2
字串 ((()()) 左括弧 : 4 >= 右括弧 : 3
字串 ((()())) 左括弧 : 4 >= 右括弧 : 4
Ex. 不合法匹配 (()))(
字串 ( 左括弧 : 1 >= 右括弧 : 0
字串 (( 左括弧 : 2 >= 右括弧 : 0
字串 (() 左括弧 : 2 >= 右括弧 : 1
字串 (()) 左括弧 : 2 >= 右括弧 : 2
字串 (())) 左括弧 : 2 <= 右括弧 : 3
!!! 右括弧次數大於左括弧了! (()))( 為不合法匹配
Input ：
輸入一個正整數 N ， 1 =< N <= 13 。
N 代表有幾組括號要匹配
Ex:
N = 1 代表 一組括號 ()
N = 2 代表有兩組括號 ()()
Output ：
輸出 N 組括號的所有合法匹配組合
輸出方式請見範例
Sample Input ：
1
2
3
4
Sample Output:
()
(())
()()
((()))
(()())
(())()
()(())
()()()
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
Method1: brute force
圖和程式以LENTH=4為例
先將所有可能列舉出來,再用程式判斷是否合法(balanced parentheses problem)
#include <iostream>
#include <cstdio>
#include <stack>
#define LENGTH 4
using namespace std;
bool islegal(char str[]){
stack<char> s;
for(int i = 0 ; i < LENGTH ; i++){
if( str[i] == '(' )
s.push('(');
else if(str[i] == ')' ){
if(s.empty() || s.top() != '(')
return false;
else
s.pop();
}
}
if(s.empty())
return true;
return false;
}
void backtrack(char str[],int index){
//index為第幾個格子
if(index == LENGTH){
str[LENGTH] = '\\0';
if(islegal(str))
cout << str << endl;
return;
}
str[index] = '('; //格子放open paren
backtrack(str , index + 1); //繼續窮舉
str[index] = ' '; //還原
str[index] = ')'; //格子放close paren
backtrack(str , index + 1); //繼續窮舉
str[index] = ' '; //還原
}
int main(){
char str[LENGTH + 1];
backtrack(str, 0);
}
觀察之後可以發現,若此括號字串長度為n, islegal(.)檢查是否合法所花的時間為O(n),共要列舉2^n,所以總共花的時間為O(n * 2^n)
Method2: prune and bound
圖和程式以LENTH=4為例
- 為了方便,以下
(皆以open paren一詞取代,(皆以close paren一詞取代 - 一個狀態代表一個長方形格子(4個子格子)
括號匹配問題中,在每一個狀態下一定都是先放open paren到格子裡,若先放close paren則之後不管放什麼皆無法balanced, ex:第一個格字為open paren,則後面不管放多長或放什麼皆無法balanced.所以在任何狀態close paren數量大於open paren數量才有可能balanced.
另一個限制,若是open paren和close paren數量沒有相等則無法達成balanced,若總長度為L(L為偶數,若L為奇數則不可能balanced,無需探討)則open paren和close paren長度不超過L/2.
總結:
若open paren數量為l,close paren數量為r,字串長度為L
- 若在某個狀態遇到
r > l,則不可能balanced,所以這條路不需繼續走 - 若字串長度為L,在每一個狀態下
l <= L/2andr <= L/2
由上述兩條可知:
- 放入
open paren之前(not 之後)要符合l < L/2之限制 - 放入
close paren之前(not 之後)要同時符合r < L/2和l > r,因為滿足l > r則一定會滿足r < L/2所以只要符合l > r即可
implementation
剛剛我們講到l與r分別是open paren數量和close paren數量,為了記住l與r所以我們將函數設計成void backtrack(char str[],int index ,int left, int right),int left和int right分別是l和r.
#include <iostream>
#include <cstdio>
#include <stack>
#define LENGTH 4
using namespace std;
void backtrack(char str[],int index ,int left, int right){
if(index == LENGTH){
str[LENGTH] = '\\0';
cout << str << endl;
return;
}
if(left < LENGTH/2){
str[index] = '(';
backtrack(str , index + 1 , left + 1 , right);
str[index] = ' ';
}
if(left > right){
str[index] = ')';
backtrack(str , index + 1 , left , right + 1);
str[index] = ' ';
}
}
int main(){
char str[LENGTH + 1];
backtrack(str, 0,0,0);
}
Sol
以上皆以LENGTH=4(即 N=2)為例,以下程式為此題的AC解,可上傳
#include <iostream>
#include <deque>
#include <cstdio>
using namespace std;
deque <char> qu;
int num;
void pa(int,int,int);
int main(){
while(cin >> num){
pa(0,0,0);
cout <<endl;
}
}
void pa(int le,int ri,int n){
if (n==2*num){//終止遞迴
for(int i=0;i<2*num;i++) printf("%c",qu[i]);
printf("\\n");
return;
}
if (le<num) {//le表示已經加入的左小括號個數，從0開始不能超過或等於num
qu.push_back('(');
pa(le+1,ri,n+1);//多了一個左小括號le+1，n+1為已經加入的左與右小括號個數
qu.pop_back();
}
if ((le>ri)&&(ri<num)) {//左小括號要大於右小括號數，且右小括號數要小於num
qu.push_back(')');
pa(le,ri+1,n+1);//多了一個右小括號ri+1，n+1為已經加入的左與右小括號個數
qu.pop_back();
}
}
