子集问题

问题

假定集合为 (1 2 3), 它的所有子集的集合就是 ( () (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3) ) 给定一个集合,求所有子集的集合

思路

总的子集 = 总的子集(有 "1" 元素)+ 总的子集(除了 "1" 元素),以 (1 2 3) 集合为例

子问题边界情况:
集合为 null,返回 (list nil)
例如元素 1 与所有除了元素 1 的所有子集组成集合的时候,1 与 null 正好形成 (1)

代码

(define (subsets s)
  (if (null? s)
      (list nil)                    ; 边界
      (let ((rest (subsets (cdr s))))
        (append rest                ; 除了第一个元素的所有子集
                (map (lambda (x)    ; 有第一个元素的所有子集
                       ; 第一个元素和除了第一个元素的所有子集组成集合
                       (append (list (car s)) x))
                     rest)))))