# forming two teams

• Jun 18th 2011, 01:56 AM
pranay
forming two teams
hi, if we have a set of n players(where n can be of the order of 10^6) whose strengths are given , then how can one check if it is possible to choose amongst these players some players(or all) such that we can form two teams each of whose total strength is the same?
the strength of a team is the sum of strengths of individual members.
E.g:
if we players with strengths 10,20,30 and 40 then we can form such two teams by selected players with strengths (10,20) in one team and with 30 in the other team.
Do we need to use median here?
Thanks.
• Jun 19th 2011, 03:52 AM
SpringFan25
Re: forming two teams
what is the range of possible strengths? are they continuous or discrete?

If they are discrete and the number of possible values is less than n, then you dont need to check. If they are continuous you can fudge the answer to within a given tolerance with similar reasoning.
• Jun 19th 2011, 10:35 AM
pranay
Re: forming two teams
Quote:

Originally Posted by SpringFan25
what is the range of possible strengths? are they continuous or discrete?

If they are discrete and the number of possible values is less than n, then you dont need to check. If they are continuous you can fudge the answer to within a given tolerance with similar reasoning.

the values are discrete and can be any number ( less than 10^9) . Sorry but i couldn't get what you meant by "you don't need to check" .Could you please explain.
• Jun 19th 2011, 10:41 AM
SpringFan25
Re: forming two teams
Quote:

Sorry but i couldn't get what you meant by "you don't need to check" .Could you please explain.
if they were discrete and the number of possible values was less than n, then at least two players must have the same score. You could play hose two players against each other. However since this isn't the case here it wont work.

Assuming you need an exact solution, I dont know how to solve your problem other than by trying every possible combination.