原題目在,若對於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 ：

1234

Sample Output:

() (())()() ((()))(()())(())()()(())()()()(((())))((()()))((())())((()))()(()(()))(()()())(()())()(())(())(())()()()((()))()(()())()(())()()()(())()()()()

Method1: brute force

圖和程式以LENTH=4為例

先將所有可能列舉出來,再用程式判斷是否合法(balanced parentheses problem)

#include 
    
     #include 
     
      #include 
      
       #define LENGTH 4using namespace std;bool islegal(char str[]){    stack
       
         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

1. 若在某個狀態遇到 r > l,則不可能balanced,所以這條路不需繼續走

2. 若字串長度為L,在每一個狀態下 l <= L/2 and r <= L/2

由上述兩條可知:

1. 放入open paren之前(not 之後)要符合l < L/2之限制

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 
    
     #include 
     
      #include 
      
       #define LENGTH 4using 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 
    
     #include 
     
      #include 
      
       using namespace std;deque 
       
         qu;int num;void pa(int,int,int);int main(){  while(cin >> num){    pa(0,0,0);    cout <
        
         ri)&&(ri
        
       
      
     
    

Reference