SICP Exercise 2.41: Triple Sum

Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

This bears some resemblance to the prime-sum-pairs procedure in the "Nested mappings" section and exercise 2.40. This time, however, we want to generate triples of integers, i, j, and k, such that 1 ≤ i < j < k ≤ n and i + j + k = s.

We already have a procedure, unique-pairs, that will generate all unique ordered pairs of distinct positive integers less than or equal to a given value. We can use this as the basis for building the triples. All we need to do is for each k, such that 3 ≤ k ≤ n, generate the unique pairs of distinct positive integers less than k (using unique-pairs), add k to each of these pairs to give all of the valid triples for that value of k and then append the results for all values of k together. And the authors have handily provided a procedure, flatmap, that encapsulates the "map and accumulate with append" process. Here's the snippet:

(flatmap (lambda (i)
                 (map (lambda (j) (cons i j))
                      (unique-pairs (- i 1))))
         (enumerate-interval 3 n))

Now all we need to do is to filter this to those triples whose sum is s and wrap it in a procedure:

(define (triples-equaling s n)
  (filter (lambda (x)
                  (= (+ (car x) (cadr x) (caddr x)) s))
          (flatmap (lambda (i)
                           (map (lambda (j) (cons i j))
                                (unique-pairs (- i 1))))
                   (enumerate-interval 3 n))))

Let's try it out:

> (triples-equaling 10 10)
'((5 3 2) (5 4 1) (6 3 1) (7 2 1))
> (triples-equaling 15 10)
'((6 5 4) (7 5 3) (7 6 2) (8 4 3) (8 5 2) (8 6 1) (9 4 2) (9 5 1) (10 3 2)
  (10 4 1))
> (triples-equaling 6 3)
'((3 2 1))
> (triples-equaling 10 5)
'((5 3 2) (5 4 1))