After my initial comment (where I suggest that it might not be enough info) I believe I actually came up with an idea.
Start with the full set of pokemon. For every possible type, identify the count of pokemon that are strong against that type. For this, you'll end up with a List<(pokemonId, types, List<weakAgainst>)>.
Minimize List<weakAgainst>.Count() and from the possible set of pokemonIds, select one at random. Without knowing anything else besides type, this pokemon is as good as any other with the same weakness count (this is the point of my original comment).
From the list of weaknesses that this selected pokemon has, select a pokemon from your list that is strong against the weakness, minimizing the amount of weaknesses again. Likely more than one will match this criteria, again, select one at random.
Keep repeating this pattern until you obtain the 6 in your team. This is, statistically speaking, one of the best teams that you can gather.
For all the combinations that you might find here, some teams will have less weaknesses, since we're "randomly" walking down a tree of possibilities. This very much sounds like a minimax-prunning algorithm, where each pokemon selection (minimizing your weaknesses) can be met with potential opponents that will maximize your weak points.
Simplified, put together:
input: allPokemon: list<pokemonId, weakAgainst, strongAgainst>
var: teamWeakAgainst: []
var: teamStrongAgainst: []
var: selectedTeam: []
while (size(selectedTeam) < 6)
goodMatches <- allPokemon.max(p -> size(p.strongAgainst.intersect(teamWeakAgainst)))
goodMatches <- goodMatches.min(p -> size(p.weakAgainst))
goodMatches <- goodMatches.max(p -> size(p.strongAgainst))
selectedPokemon <- goodMatches.random()
teamWeakAgainst -= selectedPokemon.strongAgainst
teamWeakAgainst += selectedPokemon.weakAgainst # not counting previously selected pokemon because the current one adds another "weakness", even if it was already accounted for
selectedTeam += selectedPokemon
output: selectedTeam
From this algorithm is it not obvious where the "max" portion is. We're minimizing our losses (weaknesses) but we're considering all possible opponent teams equally, so there is no real maximization of the opponent choices. For a set of ideas, check below.
Note that this algorithm will give you a set of "teams" that are equally good in the sense that they'll have the same amount of minimized weaknesses and maximized strengths against other possible teams. But even if pokemon are different, the numbers will be the same, just different types.
For a more complex approach, you might want to consider how prevalent some pokemon are (you might not need to optimize against a super rare mythical type, but rather the very common types available in the game), how likely is it that certain pokemon can have better / faster attacks, what is the probability of battle IVs, how frequent can a trainer switch pokemon in battle, etc. Again, I know this is not what you asked for, but for the sake of the example, this will become so complex that instead of a search algorithm, a simulation (Monte Carlo?) approach might be simpler to build teams out of statistical testing.
