2
給定自然數的有限序列。確定是否有可能將數字分成兩個子集，例如兩個子集的總數相等。顯示這種分配的一個變體。有初始設置，總的100將數字集合分成兩組，總數相等
的子集，我只看到了問題的一個蠻力alorithm - 檢查所有S（N，2）（第二類Stirling數）的總數爲組合平等和展現一個這樣的組合。還要檢查初始設置的所有可能組合是否等於100.是否有更優雅的解決方案？
A
回答
4
由於這是一個NP-Complete Partition Problem沒有多項式時間解決方案。但是如果你的總和不夠大，那麼有一個dp解決方案，其複雜度爲O(sum*n)，其中n是元素的數量。在這裏你可以找到solution。
相關問題
- 1. 將兩個不相等的數組組合成哈希值
- 2. 給定兩組數字，找出總和相等的最小集合
- 3. 將n個數字分成兩組，每組的總和小於等於k
- 4. 兩個數組總是相等
- 5. 將數據集劃分爲兩個聚類，總等差異相等
- 6. 組合兩個不相等的數組
- 7. 找到兩個線性相等成立的整數集合
- 8. 將一個整數的數字分成1,2,3，等數字組
- 9. 在紅寶石中將數組拆分成相等部分
- 10. 將數組分成兩部分。預定的大小，可能並不總是相等的
- 11. 將3d角度分成相等數量
- 12. Matlab：將大塊數據隨機分成相等大小的集合
- 13. Coldfusion將數組分成兩部分
- 14. 將一個數組劃分爲兩個相等大小的子集，它們的總和差值最小
- 15. 從數組中刪除任何一個元素後，將奇數大小的數組分成兩組相等大小和相同的總和
- 16. 將數據拆分成等義的組
- 17. 將兩個字符串數組相互組合
- 18. 將字母和數字的數組分割成兩個單獨的數組
- 19. 如何將一個數組分成兩部分，這兩部分的平均值相等？
- 20. 將一個集合分爲兩個不相交的子集（所有組合）
- 21. 確定集是否相等（套組成的集合）
- 22. 將集合分配到數組中
- 23. 數字組合的總和
- 24. 將兩個數組組合成一個數組
- 25. 將兩個數組組合成選項數組
- 26. 分割整數分成相等的塊
- 27. Python將值行分成兩個數組
- 28. 將一組數字分成兩部分，其中差異最小
- 29. 把數組分成兩個數組
- 30. 集合中字段總數最多的組合
你可以在這裏找到幾個更優雅的解決方案：http://stackoverflow.com/q/32354215/1009831。至於subset-100，只需在該集合中添加一個新元素（value = sum-2 * 100），然後將其分成兩個相等的子集。 –