Printing out a tree set using pattern matching in Scala
Some ideas:


Make the trait sealed.
combine doesn't need to be a nested function, this only makes it harder to read and causes problems with shadowed variables. Instead you could move it to an accompanying object, or make it a separate method such as:

sealed trait IntSet {
    ...
    private def combine(withRight: IntSet): IntSet;
}


for EmptySet it will just return withRight, for a NonEmptySet it will be

 def combine(withRight: IntSet): IntSet =
    NonEmptySet(elem, left.combine(right), withRight);

toString is somewhat complicated, and can suffer from performance problems due to repeatedly concatenating strings together. Instead I'd suggest you to implement Traversable. Not only this will make your class much more useful, it's implementation will be cleaner, because it won't be cluttered by operating with strings. And then you'll already have mkString which you can use as

override def toString: String = mkString("{", ",", "}")