Subsets

Given a set of things, a subset contains zero or more of its elements, without duplicates. As was true for ice cream bowls, order doesn't matter.

{Banana, Apple} is the same subset as {Apple, Banana}.

For example, given the set {Apple, Orange, Banana} there are one-element subsets like {Banana} and two-element subsets like {Apple, Banana}. The original set {Apple, Orange, Banana} counts, and so does the empty set {} with zero elements.

  1. Write down all the subsets of {Apple, Orange, Banana}. How many are there?
  2. Write down all the subsets of {Pretzel, Apple, Orange, Banana}. Try to do this with as little work as possible.
  3. Now create a subsets block that takes a list as input and reports a list of lists in which each item is a subset of the original input list. The order in which the subsets appear in the output list doesn't matter, but each subset must appear exactly once. The result might look like this:
    subsets of {Apple, Orange, Banana}

    If you're stuck after trying as many ideas as you can think of, go to this page for some help.