# Python3.6+
def subsets(xs: list) -> list[list]:
def select(es: list, n: int) -> list[list]:
if len(es) < n:
return []
return select(es[:-1], n) + [h+[es[-1]] for h in select(es[:-1], n-1)] if n else [[]]
return [select(xs, i+1) for i in range(len(xs))]
subsets(list('abcd'))
Out[2]:
[[['a'], ['b'], ['c'], ['d']],
[['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'd'], ['b', 'd'], ['c', 'd']],
[['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd']],
[['a', 'b', 'c', 'd']]]//
scala> "abcd".toSet.subsets.toSeq
val res1: Seq[Set[Char]] =
List(Set(),
Set(a), Set(b), Set(c), Set(d),
Set(a, b), Set(a, c), Set(a, d), Set(b, c), Set(b, d), Set(c, d),
Set(a, b, c), Set(a, b, d), Set(a, c, d), Set(b, c, d), Set(a, b, c, d))//
scala> def subsets[A](xs: Seq[A]): Seq[Seq[A]] =
| def select(es: Seq[A], n: Int): Seq[Seq[A]] = es match
| case Seq() => if n == 0 then Seq(Nil) else Seq()
| case h :+ t => select(es.init, n) ++ select(es.init, n-1).map(s => s :+ t)
| (1 to xs.size).flatMap(i => select(xs, i))
|
def subsets[A](xs: Seq[A]): Seq[Seq[A]]
scala> subsets("abcd")
val res2: Seq[Seq[Char]] = Vector(List(a), List(b), List(c), List(d), List(a, b), List(a, c), List(b, c), List(a, d), List(b, d), List(c, d), List(a, b, c), List(a, b, d), List(a, c, d), List(b, c, d), List(a, b, c, d))