基於迭代比遞迴來得快，我實作了一個迭代的版本，不過時間好像都卡在輸出部分因此沒有什麼幫助，為了解決輸出問題，我將所有要印的字串全都先放在string裡，最後再一次輸出，這樣能減少 system call 的次數而讓程式更快這在遞迴方法裡很
難辦到，而在我電腦上執行的時間也有相當的改進，只是放到server端執行時仍然是TLE，不明所以... 不過我還是想分享一下:)
(題外話: 在我的電腦上當輸入到 10 時，因為作業系統沒辦法在一個時間片段裡印完所有資料，所以輸出會被中斷，這會使得輸出是一塊一塊地被印出來)
我的方法是這樣的:
以 0 代表左括號、以 1 代表右括號
限制: 不管在任何位置，左邊 0 的總數都必須大於等於 1 的總數，也可以說成，不管在任何位置，右邊 1 的總數都必須大於等於 0 的總數
接著假設我們要印 N 組括號，並設一個數字 d 為 dN-1 ~ d0 (ex: N = 3， d = d2d1d0)， d0 代表從右邊算起第1個右括號的右邊共有幾個左括號，同理類推
推論: 因第 n+1 個右括號的右邊有 n 個右括號，由限制可推得 dn (第 n+1 個右括號) 右邊至多只能有 n 個左括號，所以 dn <= n --- 1
接著因累加的關係前面的左括號總和不可能大於後面的左括號總和，所以 dN-1 >= dN-2 >= ... >= d2 >= d1 >= d0 --- 2
演算法: (以 N = 3 為例)
第一步: 用規則一和二生成所有可能數字
結果: 000
100
110
200
210
第二步: 根據定義印出括號
ex: 210 代表第 1 個右括號右邊有 0 個左括號， 第 2 個到第 1 個右括號之間有 1-0=1 個左括號， 第 3 個到第 2 個右括號之間有 2-1=1 個左括號， 最後補上 3-2=1 個尚未被印出的左括號，得到 ()()()
結果: 000 ---> 000 ---> ((()))
100 ---> 100 ---> (()())
110 ---> 010 ---> (())()
200 ---> 200 ---> ()(())
210 ---> 110 ---> ()()()
最後反正程式碼是TLE，附上應該沒關係吧lol
#include <iostream>
#include <string>
//#include <time.h>
using namespace std;
void brackets_generator(int);bool compute_next_number(int, int *, int &);
bool compute_next_number(int, int *, int &);
void show(int, const int *, string &s);
int main()
{
//time_t t1, t2;
int N;
while(cin >> N){
//t1 = clock();
brackets_generator(N);
//t2 = clock();
//cout << "time cost: " << t2-t1 << "\n";
cout << "\n";
}
return 0;
}
bool compute_next_number(int N, int *number, int &index)
{
if (index == N)
return false;
// find next number
int check = number[index];
int pos;
for(pos=index; pos<N-1; ++pos){
if(number[pos+1] != check)
break;
}
++number[pos];
for(int i=1; i<pos; ++i)
number[i] = 0;
// update index
for(index=1; index<N; ++index)
if(number[index] != index)
break;
return true;
}
void show(int N, const int *number, string &s)
{
for(int i=0; i<N-number[N-1]; ++i)
s = s + "(";
for(int i=N-1; i>0; --i){
s = s + ")";
for(int j=0; j<number[i]-number[i-1]; ++j)
s = s + "(";
}
s = s + ")" + "\n";
}
void brackets_generator(int N)
{
string s;
int *number = new int[N];
int index = 1;
for(int i=0; i<N; ++i)
number[i] = 0;
show(N, number, s);
while(compute_next_number(N, number, index))
show(N, number, s);
cout << s;
delete number;
}