[其他] 將一數字拆解成幾種數字之合

[wandering25 (晃晃)]

題目是

給定1<=n<=100，求n能拆解成幾種數字之和的組合

例如5可以拆成

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

共五種


其實是個程式設計題目

小弟順手解了之後發現n>8之後的答案都錯了

卻找不到錯誤在哪

1. 9
2. 8+1
3. 7+2
4. 7+1+1
5. 6+3
6. 6+2+1
7. 6+1+1+1
8. 5+4
9. 5+3+1
10.5+2+2
11.5+2+1+1
12.5+1+1+1+1
13.4+4+1
14.4+3+2
15.4+3+1+1
16.4+2+2+1
17.4+2+1+1+1
18.4+1+1+1+1+1
19.3+3+3
20.3+3+2+1
21.3+3+1+1+1
22.3+2+2+1+1
23.3+2+1+1+1+1
24.3+1+1+1+1+1+1
25.2+2+2+2+1
26.2+2+2+1+1+1
27.2+2+1+1+1+1+1
28.2+1+1+1+1+1+1+1
29.1+1+1+1+1+1+1+1+1


上面是我跑出來n=9時所有狀況
(抱歉有點眼花撩亂)
共29組
但答案是30組
但我看不出來是少了哪一組耶?

最主要是想請問這樣的題目
大家會用怎麼樣的思維去想?
因為我的code有點徒法煉鋼一組一組找出來
覺得有點慢

謝謝大家

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.131.228
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1425407449.A.BAD.html
※ 編輯: wandering25 (61.230.131.228), 03/04/2015 02:31:26
推 turboho     : 少3+2+2+2
→ turboho     : 寫code要寫短一點的話可以寫遞迴吧
推 turboho     : wikipedia的partition(number theory)有寫很多東西
推 LPH66       : 就把這 30 組依照最大數字是誰分組分開
→ LPH66       : 每一組內扣掉最大數字後等於剩下的數在某些條件下的
→ LPH66       : 拆分組合, 這裡就是遞迴上場的時候了
推 Giawgwan    : 缺 3+2+2+2
推 yueayase    : 這是online judge的題目嗎?