CODEWITHSUNDEEP
algorithmsorting
arvin
arvin

Reputation: 43

Algorithm to find the set when the set of sums of subsets of power set is given

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?

Upvotes: 1

Views: 526

Answers (1)

Nilesh
Nilesh

Reputation: 1343

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.

Upvotes: 2

Related Questions