Lispology

About me

Feeds

Recursive solution to Subset Sum

8th September 2025

I recently wanted to find an NP-hard problem that was expensive to calculate, to demonstrate the speed advantage of a compiled Lisp, and found the Subset Sum problem ^[1].

The problem is as follows: given a list of integers and a target total, find whether the target can be reached by summing a subset of the integers.

Here's the most succinct solution I could write in Lisp:

(defun subsetsum-p (lis n sum)
  (cond
   ((zerop sum) t)
   ((zerop n) nil)
   ((> (nth (1- n) lis) sum) (subsetsum-p lis (1- n) sum))
   ((subsetsum-p lis (1- n) sum))
   (t (subsetsum-p lis (1- n) (- sum (nth (1- n) lis))))))

where lis is a list of integers, n is the length of that list, and sum is the target sum we are trying to reach. The function returns t if there is at least one subset with the target sum, and nil otherwise.

For example, we can define the list as follows:

(defparameter *lis* '(2 4 6 8 10 12 14 16 18 20 22 24 26 28 30))

and then test the function with:

> (subsetsum-p *lis* (length *lis*) 200)
T

> (subsetsum-p *lis* (length *lis*) 199)
NIL

Here I've contrived the list to only contain even numbers, so we can be sure that 199 will be unreachable.

How it works

The function calls itself recursively with a shorter list and a reduced sum:

If the target sum is now zero we've reached the target, so return t.
If n is zero we've run out of numbers to test, so return nil.
If the last number in the list is greater than sum, call subsetsum-p with that number dropped from the list.
Otherwise try calling subsetsum-p using all but the last number in the list, and if that fails try using the last number.

Displaying a result

It's a simple change to the function to make it return the first solution:

(defun subsetsum-p (lis n sum result)
  (cond
   ((zerop sum) result)
   ((zerop n) nil)
   ((> (nth (1- n) lis) sum) (subsetsum-p lis (1- n) sum result))
   ((subsetsum-p lis (1- n) sum result))
   (t (push (nth (1- n) lis) result)
      (subsetsum-p lis (1- n) (- sum (nth (1- n) lis)) result))))

We now call it with result initially set to nil, and the function returns a list of numbers that reach the target:

> (subsetsum-p *lis* (length *lis*) 200 nil)
(2 4 6 8 12 14 16 18 20 22 24 26 28)

There may be multiple solutions; this function only returns the first one found.

Update

The solution can be made shorter by omitting the test that the last number in the list is greater than sum; the function is actually faster without it, so the new version is:

(defun subsetsum-p (lis n sum)
  (cond
   ((zerop sum) t)
   ((zerop n) nil)
   ((subsetsum-p lis (1- n) sum))
   (t (subsetsum-p lis (1- n) (- sum (nth (1- n) lis))))))

^ Subset sum problem on Wikipedia.

Previous: Improving truncate