推 Huangs:這個方法就是暴力展開所有組合。如果只是要算總數用DP就好 02/27 12:05
→ Huangs:或者在這個遞迴裡加上 memoization，複雜度差很多。 02/27 12:05
推 Huangs:另外這篇的方法似乎會產生重覆的組合(例如 1 2 和 2 1) 02/27 12:08
→ ledia:還會取同一個... 02/27 12:28
→ Baudelaire:所以說如果不要sequence就用int[] count啊 02/27 13:34
推 Huangs:把result改成count一樣要展開全部的排列，而且加總值是錯的 02/27 13:49
→ Huangs:因為會多算重覆的組合 02/27 13:49
講的太簡單了，如果要直接算結果而不考慮順序，
可以寫成這樣：
static void sumupArray2(int[] array, int num, int[] result, int cursor)
{
if (num == 0)
{
System.out.println(Arrays.toString(result));
return;
}
if (num < 0 || cursor == array.length)
{
return;
}
int count = 0;
while(num >= 0)
{
result[cursor] = count++;
sumupArray2(array, num, result, cursor+1);
num -= array[cursor];
}
}
總之就是遞迴啦，遞迴的問題主要在於可能會爆掉，
不過在interview的時候只要提到這一點，其實還滿好用的...。
→ yauhh:重複組合沒問題啦,你想,有三題三個分數1:5分,2:10分,3:5分, 02/27 18:08
→ yauhh:4:5分,求合計10分會得到(5,5),(5,5),10,(5,5),這是重複嗎? 02/27 18:09
→ yauhh:其實是(1:5,3:5),(1:5,4:5),2:10,(3:5,4:5),沒有重複啊 02/27 18:10
→ yauhh:而且解題是在面試中即時對話進行,這種額外資訊很好解釋的. 02/27 18:11
--
Je t'aime,o capitale infame.
Tu m'as donne ta boue et j'en ai fait de l'or.
Charles Baudelaire 1821-67
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.22.103.54
推 manlike:恐怖.. 無窮遞迴 @@ 02/28 00:29
→ manlike:喔 多了cursor @@? 看不懂在幹麻! XD 02/28 00:31
→ manlike:感覺就是錯的~ cursor==array.length 就停是啥意思...XD 02/28 00:33
→ Baudelaire:抓下來跑跑看吧... debugger很好用的... 02/28 01:27
→ manlike:沒興趣 XD 02/28 01:30
→ Baudelaire:只能跟你說你的感覺錯了，答案是對的 02/28 01:51
推 yauhh:乍看是無窮遞迴,其實有用到二個底,應該會停吧 02/28 01:51
推 ledia:下一題就是怎麼改成非遞迴了 XD 02/28 15:00
→ Baudelaire:非遞迴的答案很簡單，這裡地方不夠寫了... XD 02/29 07:55
→ yauhh:關於遞迴,我覺得就像是變數容量一樣的限制, 在限定範圍中 02/29 10:46
→ yauhh:不會是問題. stack overflow 和 buffer overflow,都不是 02/29 10:47
→ yauhh:靠著一開始寫一二行程式碼就可以徹底避開. 02/29 10:48