You don't need to fully perform the union of each pair: abandon the union computing process on first missing item, e.g.
Suppose
k=5, s1 = {1,2,5}, s2 = {1,4}
since
3
is missing in both
s1
and
s2
then you don't have to fully perform the union of the two sets to discover they are bad candidates.