Partition of a set into K disjoint subsets with equal sum

Question

Given n ( n <= 20) non-negative numbers. Is there / Can there be an algorithm with acceptable time complexity that determines whether the n numbers can be divided into K ( K <= 10) disjoint subsets, such that each subset has equal sum?

Answer 1

One way to improve on the brute force method:

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

The hard (and slow) part is generating the partitions. You can do this with a recursive function. It shouldn't be unreasonably slow for partitioning 20 numbers. You can optimize the partition generation by throwing out partitions with unequal subset sums early.