問(wèn)題:左“{”，右”}"括號(hào)各N個(gè)，請(qǐng)打印出所有正確的組合，比如當(dāng)N=3，{}{}{}，{}{{}}，等為正確的組合。如果寫的代碼是recursive，能否用iterative再寫一個(gè)；反之亦然。py實(shí)現(xiàn):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貢獻(xiàn)1805條經(jīng)驗(yàn) 獲得超9個(gè)贊
這個(gè)很容易就可以想到用回溯法來(lái)做。假設(shè)從左往右填括號(hào)。
狀態(tài)包括：
(1) 填到第幾個(gè)：int i
(2) 在右邊最多還能填多少個(gè) "}"：int left
(3) 還剩多少個(gè)"{"可以填：int a
(4) 還剩多少個(gè)"}"可以填：int b
具體策略：
(1) 如果已經(jīng)填完了，輸出，返回（回溯）
(2) 如果還有"{"可以填：填進(jìn)去，遞歸填下一個(gè)。
(3) 如果還可以填"}"并且還有"}"可以填：填進(jìn)去，遞歸填下一個(gè)。
實(shí)現(xiàn)的代碼附在后面。
至于轉(zhuǎn)化成迭代的方式，任何遞歸都可以通過(guò)引入棧的方式來(lái)轉(zhuǎn)化，只是寫起來(lái)比較痛苦，看起來(lái)也比較痛苦就是了。
#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;
}添加回答
舉報(bào)
0/150
提交
取消