推 manlike:所以這是不能重複選的答案 XD 02/28 01:27
→ Baudelaire:感謝註解 XD 02/28 01:28
推 yauhh:第一次看到回文是幫前文徹底註解 02/28 01:37
推 genius945:幫註解XD 02/28 16:02
public static void main(String[] args)
{
sumupArray2(new int[]{2,3,7}, 100, new int[3], 0);
}
//array: all possible points
//num: final score
//result: counter for each possible points in the array
//cursor: an index for array
:
: static void sumupArray2(int[] array, int num, int[] result, int cursor)
: {
//if num ==0 which means the combination is correct, print it.
: if (num == 0)
: {
: System.out.println(Arrays.toString(result));
: return;
: }
:
//if num < 0 or cursor == array.length which means either
//the combination we choose does not sum up as num
//or there is no more number in the array to take
: if (num < 0 || cursor == array.length)
: {
: return;
: }
:
//for each possible point in the array
: int count = 0;
:
//take as many times as possible for the point of array[curosr]
: while(num >= 0)
: {
//array[curosr] is taken 'count' times, and increase the counter
: result[cursor] = count++;
//recursive, pass the current result and move cursor to next
//possible point in the array.
: sumupArray2(array, num, result, cursor+1);
//calculate how many total score left.
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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.17.211.107