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).
public Iterator<E> iterator() {
      return new UnmodifiableIterator<E>() {
        final ImmutableList<E> elements = inputSet.keySet().asList();
        int remainingSetBits = mask;
        @Override
        public boolean hasNext() {
          return remainingSetBits != 0;
        }
        @Override
        public E next() {
          int index = Integer.numberOfTrailingZeros(remainingSetBits);
          if (index == 32) {
            throw new NoSuchElementException();
          }
          remainingSetBits &= ~(1 << index);
          return elements.get(index);
        }
      };
    }
    @Override
    public int size() {
      return Integer.bitCount(mask);
    }
    @Override
    public boolean contains(@Nullable Object o) {
      Integer index = inputSet.get(o);
      return index != null && (mask & (1 << index)) != 0;
    }
  }
  private static final class PowerSet<E> extends AbstractSet<Set<E>> {