combinations.scala

object Combine {
  def linear[A](xs: Seq[A]): Seq[Seq[A]] =
    xs match {
      case Seq() => Seq(Seq())
      case Seq(h, t @ _*) =>
        linear(t) flatMap { ts => Seq(ts, h +: ts) }
    }

  def binary[A](xs: Seq[A]): Seq[Seq[A]] =
    xs match {
      case Seq() => Seq(Seq())
      case Seq(x) => Seq(Seq(), Seq(x))
      case xs =>
        val (ls, rs) = xs.splitAt(xs.length / 2)
        for (l <- binary(ls); r <- binary(rs)) yield l ++ r
    }
}

Combine.linear(Seq.range(1, 5)) foreach println
println("-" * 10)
Combine.binary(Seq.range(1, 5)) foreach println