題目連結:
題目大意:
第一列給定一正整數 N (3 ≦ N ≦ 16),代表有 N 個寶物。接著一列給定 N 個正整數(皆小於 10 ^ 7),代表這 N 個寶物的價值。
試問,是否可以將這 N 個寶物分給三個人(每個寶物都要分給其中一個人)並使得每個人得到的寶物價值總和皆一致?
範例輸入:
範例輸入 1:
3
1 2 3
範例輸入 2:
4
1 2 3 3
範例輸入 3:
10
12 53 34 23 29 26 19 10 1 6
範例輸出:
範例輸出 1:
NO
範例輸出 2:
YES
範例輸出 3:
YES
解題思維:
直接窮舉出所有 3 ^ N 種的分配情況,也就是第一個寶物看要分給誰、第二個要給誰、……遞迴到最後一個寶物為止。然後如果有出現三個人的價值皆恰為總價值 ÷ 3 之值,則代表可以平分寶物的價值,輸出「YES」。
如果完全沒出現過以上的組合,則輸出「NO」。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。