Reference no: EM13330128

Suppose you have a procedure that can partition a set of positive integers into two equal weight subsets. How could you use this procedure to solve the subset-sum problem?

To solve this we use reduction. In which prove that subset-sum problem can be reduce to partition problem and visa versa.

The set B of n positive integers whose element summation is equal to an integer K.

Partition reduces to Subset Sum:

Calculate Sum = , which is the summation of all the given numbers. A partition Subset Sum if K = Sum/2.

Subset Sum reduces to Partition:

Calculate Sum = , which is the summation of all the given numbers.

Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} {x}, where the summation now is B+x. it is possible to split the numbers in A into some subsets iff they can summing up to K:

Subset sum of B indicates partition of A means the set that adds up to Sum with x form a partition.

Partition of A indicates subset sum of B means the numbers which are put together with x must add up to K. Therefore, a partition exists iff some numbers in the B add up to K.

These reference could help you :

1. Bron, C. and Kerbosch, J. "Algorithm 457: Finding All Cliques of an Undirected Graph." Comm. ACM 16, 48-50, 1973.
2. Tomita, E.; Tanaka, A.; and Takahashi, H. "The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments." Theor. Comput. Sci. 363, 28-42, 2006.