# 2.32

# SICP Exercise 2.32

This problem is similar to the count-change problem. The set of all subsets is the union of:

- the set of all subsets without the first number
- the set of all subsets without the first number, with the first number inserted into each subset

The obviyus answer is recursion.

```
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x)
(cons (car s) x))
rest)))))
```

Here’s a test case:

```
> (subsets (list 1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
```

The way it works is:

$$ \begin{align} (1 2 3) &\leftarrow (2 3) (2 3) &\leftarrow (3) (3) &\leftarrow () \end{align} $$