On my interpreter (SCM), subs and subs2 take less time, but use around 4
times as many storage cells for intermediate values.  It's a tradeoff that's
advantageous on some interpreters, I guess.

   Is Chez Scheme in Debian?

   Listing for subs2 follows:

(define (subs-base xs)
  (if (null? xs)
      ()
      (let* ((rest (subs-base (cdr xs)))
             (first (if (null? rest) () (car rest))))
        (cons (cons (list (car xs)) first) rest)
)))

(define (subs-expand xs sets)
  (if (or (null? xs) (null? sets) (null? (cdr sets)))
      ()
      (let* ((rest (subs-expand (cdr xs) (cdr sets)))
             (first (if (null? rest) () (car rest))))
        (cons
         (append (map (lambda (x) (cons (car xs) x)) (cadr sets)) first)
         rest
))))

(define (subs2 xs n)
  (if (eq? 0 n)
      ()
      (do ((i 1 (+ i 1))
           (acc (subs-base xs) (subs-expand xs acc)))
          ((eqv? i n) (car acc)))
))