Team matchmaking algorithm based on ELO

I'm looking for a very simple way to put up 2 teams out of unspecified(but known) amount of players. So its not actually a standard matchmaking since it only creates one match out of the whole pool of registered players for the specific match. I do have pretty much only single variable and it is the ELO score for each player, which means it's the only available option to base calculations on.

What I thought of is just simply go through every possible combination of a players(6 in each team) and the lowest difference between the average ELO of teams is the final rosters that get created. I've tested this option and it gives me more than 17mil calculations for 18 registered players(the amount of players shouldnt be more than 24 usually) so its doable but its definitely the MOST unoptimized way to do that.

So I decided to ask a question in here, maybe you can help me with that in some way. Any ideas what simple algos I can use or the ways of optimizing something in a straight up comparisons of all possible combinations.

If you want to provide any code examples I can read any code language(almost), so it doesnt really matter.

Update:

Input: a list[] of player that contain player_id and elo,
Output: two lists: team1[] and team2[] containing player objects.
Objective: The average Elo of both teams should be as close as possible.

Solution

Given that your approach is an approximation anyways, putting too much effort to produce a perfect answer is a losing cause. Instead pick a reasonable difference and go from there.

I would suggest that you sort the list of players by ELO, then pair them up. Those people will be on opposing teams if they are included. If there are an odd number of people, leave out the person who is farthest from any other. Sort the pairs by difference and pair them up as well in the same way. That gives you fairly evenly matched groups of 4, and the teams will be the best and worst against the middle 2. These groups of 4 should generally be relatively close to even. Score it as the better group minus the worse one. (Either half can wind up better depending on actual scores.)

Now search for 3 groups of 4 such that A is as close as possible to the sum of B and C. The better group from A will go with the worse groups from B and C.

With 24 people this will be a virtually instantaneous calculation, and will give reasonable results.

The repeated difference approach that I started with is a well-known heuristic for the subset sum problem.

Given how fast this heuristic is, I think that it is worth broadening the search for a good team as follows.

Sort your players. Put each player into a pair with the person above and below. With n players this will be n-1 pairs. Give each pair a score of either the ELO difference, or of how much more likely the better is to beat the worse. (Which I would choose depends on the way that the two play.)
Sort your pairs. Pair each pair with the closest pair above and below who does not intersect it. With n-1 pairs this will usually result in n-2 groups of 4.
Create a sorted list of groups of 4. Call it list4. Note that this list has size n + O(1).
Construct a list of all groups of 8 that can be made from 2 groups of 4 that do not intersect. Sort it. Call it list8. The formula for how big this list is is complicated, but is n^2/2 + O(n) and took time O(n^2 log(n)) to sort.
For each element of list4 find the nearest elements in list8 that are above/below it and have no players in common with it. For O(n) elements this is O(log(n)) expected work.

The result is that you get rid of the even/odd logic. Yes, you added back in some extra effort, but the biggest effort was the O(n^2 log(n)) to sort list8. This is sufficiently fast that you'll still produce very quick answers even if you had a hundred people thrown at it.

The result will be two evenly matched teams such that when they pair off by strength, the weaker team at least has a reasonable chance of posting a convincing upset.