Question

Consider the partition problem: given n positive integers, partition them into two disjoint subsets with the same sum of their elements. (Of course, the problem does not always have a solution.) Design an exhaustive-search algorithm for this problem. Try to minimize the number of subsets the algorithm needs to generate.

Answer 1

Answer:

Please see below

Explanation:

The relevant algorithm has been attached as images herein as part a and part b. There are 2 important steps in solving this query.

First, you need to acquire a sum value of the array. For an odd sum, the output will come out as false since there cannot be 2 subsets whose sums are equivalent to each other.

Second, in case of an even sum, acquire sum divided by two and locate a subset of the array that has an equivalent sum to this (use recursion or dynamic programming).