palindromePartitions.scala

  def palindromePartitions(s: String): Seq[Seq[String]] = {
    val n = s.length - 1
    
    def isPalindrome(i: Int, j: Int): Boolean =
      i >= j || s.charAt(i) == s.charAt(j) && isPalindrome(i + 1, j - 1)

    // Palindromes starting at s[i]
    def partition(i: Int): Seq[Seq[String]] =
      if (i == n + 1) Seq(Seq())           
      else for {
        j <- i to n                         // For each s[i..j] where j=i..n
        if isPalindrome(s, i, j)            // If s[i..j] is a palindrome
        ps <- partition(j + 1)              // For each palindrome starting at s[j+1]
      } yield s.substring(i, j + 1) +: ps   // Prepend s[i..j] to it

    partition(0)
  }