1

From a set A of N positive numbers, a set of Sum of all possible subsets of the set A is formed and given. We have to find the set A.

My approach is to sort first and then keep sbtracting the Nth largest number from the largest number to find the elements of the set. What is wrong with that approach?

Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
arvin
  • 43
  • 6
  • My approach is to sort first and then keep sbtracting the Nth largest number from the largest number to find the elements of the set. What is wrong with that approach – arvin Sep 03 '18 at 11:35
  • What is given if set was {1,2,3}: powerset {1,2,3,4,5,6}? {1,2,3,3,4,5,6}? – MBo Sep 03 '18 at 12:04
  • no, P({1,2,3}) = {0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} and sum set is {0,1,2,3,3,4,5,6} – arvin Sep 03 '18 at 12:23
  • Give an example of an input and output to this algorithm. – Haskar P Sep 03 '18 at 12:53
  • 2
    I would go from small to big: The smallest number in the sum set (after removing 0) will be an element of `A`. Once you find such an element, remove it and all possible sums that you can form with it and all previously found elements from the sum set and repeat. – Nico Schertler Sep 03 '18 at 13:11

1 Answers1

2

Consider the set of elements to be {a,b,c,d}, in such a case the possible subset sums of the set would be (1){a}, (2){b+c}, (3){b+c+d}, (4){a+b+c+d} and more. However the largest subset sum would be (4) and as visible, the subtraction of (4) - (2) will yield {a+d} which is just another subset sum of the set and not the actual element.

A possible way to solve the problem is to sort the array, and start picking up elements from the smallest in a sack. Every time we pick a new element, we compute all the possible subset sums possible which always includes this element and other elements from our maintained sack, and then remove these computed subset sums from the given subset sum list. We then proceed to pickup the next smallest element from the given subset list which hasn't been removed yet.

EDIT: Added possible solution to the given question.

Nilesh
  • 1,388
  • 6
  • 17