Question

What is the set partition problem?

(a) finding a subset of a set that has sum of elements equal to a given number

(b) checking for the presence of a subset that has sum of elements equal to a given number

(c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result

(d) finding subsets with equal sum of elements

This question was posed to me in homework.

The query is from Checksum, Complexity Classes & NP Complete Problems topic in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

The correct option is (c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result

Explanation: In set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such subsets are present then we print true otherwise false.