Идея следующая - загнать футбольные команды в граф, где вершины - команды, а рёбра - показатель того, что в командах есть дублирующиеся игроки, после чего задача сводится к задаче о независимом множестве (http://ru.wikipedia.org/wiki/Задача_о_независимом_множестве).
Картинка:
Там кажется, что 2 и 5 связаны - это не так. 2 и 5 по отдельности связаны с 15-ю.
В коде неоптимально вычисляется пересечение - достаточно самого факта, а вычисляем пересечение целиком. Можно заоптимизировать.
Надо сказать, что поскольку задача о независимом множестве NP-полная, а "Легенды футбола" сводится к ней за полиномиальное время, то и "Легенды футбола" NP-полная задача, и нечего комплексовать, что не можем придумать к ней оптимального алгоритма. Тут и подходят-то только поиск с возвратом, жадный поиск, A* и их друзья.
Вывод: