This was almost certainly my fault, but as I look at the implementation of Sets.cartesianProduct, I think its `contains` method made the assumption that `ImmutableSet.asList().indexOf` was O(1), which is no longer the case for Android.  It should probably get a specific `contains` implementation that actually is O(sets), not O(sets*setSize).
final ImmutableMap<E, Integer> inputSet;
    PowerSet(Set<E> input) {
      checkArgument(
          input.size() <= 30, "Too many elements to create power set: %s > 30", input.size());
      this.inputSet = Maps.indexMap(input);
    }
    @Override
    public int size() {
      return 1 << inputSet.size();
    }
    @Override
    public boolean isEmpty() {
      return false;
    }
    @Override
    public Iterator<Set<E>> iterator() {
      return new AbstractIndexedListIterator<Set<E>>(size()) {
        @Override
        protected Set<E> get(final int setBits) {
          return new SubSet<E>(inputSet, setBits);
        }
      };
    }
    @Override
    public boolean contains(@Nullable Object obj) {
      if (obj instanceof Set) {
        Set<?> set = (Set<?>) obj;
        return inputSet.keySet().containsAll(set);
      }
      return false;