0

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?

Prakhar Agarwal
  • 51
  • 7
  • I think I'm late here but this might help others who come here: https://www.techiedelight.com/k-partition-problem-print-all-subsets/ archived here: https://web.archive.org/web/20210824071902/https://www.techiedelight.com/k-partition-problem-print-all-subsets/ – humble_barnacle Aug 24 '21 at 07:16

1 Answers1

0

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.

xpda
  • 15,585
  • 8
  • 51
  • 82
  • can you please explain the part "if k is an integer then see if you can make i subsets, each adding up to k."? I mean, how to find i disjoint subsets that cover all the n numbers and each have equal sum? – Prakhar Agarwal Dec 06 '14 at 04:55
  • That's the brute force part, but since you only have to do it for a few values, it's much faster. I'll explain in the answer. – xpda Dec 06 '14 at 06:07
  • ok.. waiting for the explanation. Actually i am having difficulty in implementing the part where i have to find i disjoint subsets with equal sum. – Prakhar Agarwal Dec 06 '14 at 06:42
  • Can you please help me with the recursive partition generating function? how do i implement it? – Prakhar Agarwal Dec 06 '14 at 07:15