将一个集合划分为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个数字的速度不应该不合理。您可以通过尽早抛出不等额子集分区来优化分区生成。