將一個集合劃分爲K個不相等的子集合

Question

給定n（n < = 20）非負數。是否有/可以有一個算法具有可接受的時間複雜度，以確定是否可以將n個數分爲K（K < = 10）不相交的子集，以使每個子集具有相等的總和？

Answer 1

的一種方式，以提高在蠻力方法：

s = the sum of all the numbers 
for i = 2 to 10 
    k = s/i 

    if k is an integer then 
    Get all partitions of the input array with a minimum subset size of 2 elements and a maximum of n-1 elements. 
    Check each partition as it's generated to see if all the subsets have the same sum. 
    end if 

    next i 

硬（和慢）部分產生的分區。你可以用遞歸函數來做到這一點。劃分20個數字的速度不應該不合理。您可以通過儘早拋出不等額子集分區來優化分區生成。