(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
	(append rest (map (lambda (l) (cons (car s) l)) rest)))))

; By induction: Empty case is obvious.  Suppose we have T_n, the set of subsets of
; S_n = {s_1, ... , s_n}.  Let S_{n+1} = S + {s_{n+1}}.  Then T_n is a subset of
; T_{n+1}.  Any element of T_{n+1}\T_n must contain s_{n+1}, otherwise it would
; have been in T_n.