Please help with this algorithm... Given a set A of m distinct positive integers
ID: 3564086 • Letter: P
Question
Please help with this algorithm...
Given a set A of m distinct positive integers (using an array) as input, return true if there are two subsets of A, call these subsets S and T, such that S (union) T = A, S (intersect)T = (empty set) and (Summation)i(element of) S i = 2 * (Summation)i(element of)T i, and return false otherwise. That is, is there a way to partition the set A into two disjoint subsets S and T such that the sum of the elements in S is equal to twice the sum of the elements in T? Write in pseudo code an exhaustive search algorithm that solves this problem and explain how your algorithm works and what the runtime is.
Explanation / Answer
Problem: Two disjoint sets but exhaustive sub sets of A, such that (Sum of integers in S) = 2 * (Sum of Integers in T)
Solution : Since Sum(S) + Sum(T) = Sum (A)
=> 2Sum(T) + Sum (T) = Sum(A)
Sum(T) = Sum(A)/3
Now we have to find the group of numbers such that their sum is Sum(A)/3.
Let Sum of elements of A = x
Since all are positive integers, collect all the numbers less than x/3. Let all such no.s =y
Now chose n elements over time out of the given y elements where y belongs to (1,2,3,....(n-1))
Sum the chosen n elemnts and check if sum is x/3. If yes. Then done. Otherwise iterate again.
Psuedo Code:
Y -> No. of elemnts in A
X -> sum of elements in A.
L -> Sorted Set of elements of A which are less than x/3
Sum of elements in T = X/3
for n =1 -> y-1:
chose n elements out of L. (repeat this LCn times where LCn means Combination)
if sum = x/3
Print "Solution Exists"