CODEWITHSUNDEEP
arraysalgorithmdata-structuresset
akash
akash

Reputation: 1801

Divide the set into group of two

Given is a set of elements. You have to divide them into groups of two, such that the difference between the sum of elements of an individual group is minimum.

example:

5
4 6 7 2 1

two groups are: {4,6} and {7,2,1}.

My approach: I have come across only the brute force solution of this problem, i.e. generate all the subsets (2^n) of the set using bit shifting technique.

I am looking for a better solution.

Upvotes: 1

Views: 1489

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Instead of giving you the solution I will give you two tips:

  1. Calculate the sum of all elements and instead of solving the original problem. Denote this S. Solve a problem stated as follows - find a subset of the given numbers with sum no more than the S/2. The remaining numbers will form the other subset.

  2. The problem I describe above is very simplified knapsack problem with equal costs of all elements. Again it can be solved using dynamic programming(but in this case it will be way simpler than the one used for the classical knapsack problem)

Upvotes: 2

Related Questions