I am trying to solve the equal subset sum problem , where we have to tell if its possible to generate to disjoint subsets whose (non-zero) sum is equal and you don't have to consider all the elements. The numbers will be unique and in the range of 1-99.
I used a recursive approach of considering each element to be part of first/second/neither set. I am looking to optimize the code.
The second approach is to generate all possible sums and if any sum occurs more than once it would return true. The problem with the second approach is I am not able to prove that the sum generated is from disjoint sets.
Consider sets A = {1,2,3,4} and B = {9,1}. The sum of both the sets is 10 and they are disjoint. Is it safe to say that if we have a set of non disjoint sets whose sum is equal, can be converted into two disjoint sets of equal sum by removing the common elements. If not can somebody give me a counter example . Like in this case we will have {2,3,4} and {9}.
Best Answer
Ok, first of all: If you don't have to use all numbers, may I suggest to take $A = B = \emptyset$?
Next: We can write $$\sum_{x \in A} x = \sum_{x \in A \cap B} x + \sum_{x \in A \backslash B} x$$ and the same for $B$. This should already finish the proof as long as $A \neq B$ (if they are equal you will get the empty set mentioned above).