問題:左“{”，右”}"括號各N個，請打印出所有正確的組合，比如當N=3，{}{}{}，{}{{}}，等為正確的組合。如果寫的代碼是recursive，能否用iterative再寫一個；反之亦然。py實現:def foo(output, open, close, pairs): if open == pairs and close == pairs: print output
else: if open<pairs:
foo(output+'(', open+1, close, pairs) if close<open:
foo(output+')', open, close+1, pairs)
foo('', 0, 0, 3)
1 回答
Cats萌萌
TA貢獻1805條經驗 獲得超9個贊
這個很容易就可以想到用回溯法來做。假設從左往右填括號。
狀態包括：
(1) 填到第幾個：int i
(2) 在右邊最多還能填多少個 "}"：int left
(3) 還剩多少個"{"可以填：int a
(4) 還剩多少個"}"可以填：int b
具體策略：
(1) 如果已經填完了，輸出，返回（回溯）
(2) 如果還有"{"可以填：填進去，遞歸填下一個。
(3) 如果還可以填"}"并且還有"}"可以填：填進去，遞歸填下一個。
實現的代碼附在后面。
至于轉化成迭代的方式，任何遞歸都可以通過引入棧的方式來轉化，只是寫起來比較痛苦，看起來也比較痛苦就是了。
#include <stdio.h>const int maxn = 50;char x[maxn * 2 + 1];void perm(int i, int left, int a, int b) { if (a == 0 && b == 0) { puts(x);
return;
} if (a > 0) {
x[i] = '{'; perm(i + 1, left + 1, a - 1, b);
} if (b > 0 && left > 0) {
x[i] = '}'; perm(i + 1, left - 1, a, b - 1);
}
}int main() { int n = 4;
x [n * 2] = 0; perm(0, 0, n, n); return 0;
}添加回答
舉報
0/150
提交
取消