2

Given a finite sequence of natural numbers. Determine wether it is possible to divide the numbers into two subsets such as totals of both subsets are equal. Show one variant of such distribution. Is there a subset of initial set with total of 100.

I only see a brute force alorithm for the problem - check totals of all of S(n,2) (Stirling number of the second kind) combinations for equality and show one such combination. And also check all possible combinations of initial set for equality to 100. Is there more elegant solution?

Alexander
  • 257
  • 1
  • 3
  • 11
  • 3
    You could find several more elegant solutions here: http://stackoverflow.com/q/32354215/1009831. As for subset-100, just add a new element (with value=sum-2*100) to the set, then partition it into two equal subsets. – Evgeny Kluev Sep 22 '15 at 20:01

1 Answers1

4

As it is a NP-Complete Partition Problem there is no polynomial time solution. But if your sum is not big enough then there is an dp solution with complexity O(sum*n) where n is number of element. Here you can find the solution.

ashiquzzaman33
  • 5,781
  • 5
  • 31
  • 42