Question

Consider a variation of the balanced partition problem in which we find two subsets such that |S1 – S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?

(a) {5, 4} & {3, 2, 1}

(b) {5} & {4, 3, 2, 1}

(c) {4, 2} & {5, 3, 1}

(d) {5, 3} & {4, 2, 1}

This question was posed to me in class test.

Query is from Balanced Partition in portion Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right choice is (d) {5, 3} & {4, 2, 1}

The best explanation: For S1 = {5, 3} and S2 = {4, 2, 1}, sum(S1) – sum(S2) = 1, which is the optimal solution.