The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, the statement would be: What is the best way to return all sets from C which are a subset of search set S?

  • $\begingroup$ See cs.stackexchange.com/q/120493/755, cs.stackexchange.com/q/75915/755, as well as cs.stackexchange.com/q/7701/755, cs.stackexchange.com/q/109399/755 (take complements of all sets) $\endgroup$
    – D.W.
    Feb 24, 2022 at 7:17
  • 1
    $\begingroup$ I'm not looking for element of C to be superset of S, but for element of C to be subset of S, so the other way around. $\endgroup$
    – Vladimir
    Feb 24, 2022 at 21:52
  • 1
    $\begingroup$ If you "take complements of all sets", that swaps superset vs subset, showing a close connection between those two problems and allowing you to apply techniques for one to solve the other. $\endgroup$
    – D.W.
    Feb 24, 2022 at 22:23
  • $\begingroup$ @D.W. if the concourse is very large and each set is very small relatively, wouldn't "take complement" immediately involve a huge factor in both time and space complexity for every operation? $\endgroup$
    – SOFe


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.