## Subset Sums

### November 9, 2010

We have previously solved Part 1 and Part 2 of the Greplin Programming Challenge. In today’s exercise we will solve the third and final part:

Find all the subsets of a set of non-negative integers where the largest number is the sum of the remaining numbers, and return a count of the number of them. For instance, for the set { 1, 2, 3, 4, 6 } the subsets are 1+2=3, 1+3=4, 2+4=6, and 1+2+3=6, so the result is 4 subsets. Apply your program to the set { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99 }.

Your task is to write a program to solve the challenge. In addition to solving the challenge, you might like to apply your solution to the set of prime numbers less than 2^{10}. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[…] Praxis – Subset Sums By Remco Niemeijer In today’s Programming Praxis exercise, we have to solve the third part of the Greplin challenge, which is to […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/09/programming-praxis-subset-sums/ for a version with comments):

For the 2^10:

~/praxis$ time python greplin3.py

44586565247

real 0m0.592s

user 0m0.456s

sys 0m0.132s

Should’ve read the HOWTO post source code first before posting … sorry, and I should’ve changed f[j] = False to f[j] = 1 even though it doesn’t seem to affect the result.

I am confused that brute force should take as long as you claim. The following code brute-force searches the powerset, but runs in under four seconds (not minutes) on a

cheap (AMD M520) laptop with stklos. I suspect that since your first algorithm computes

and stores the entire powerset in order to then filter it, you are hitting the swap hard.

(define subsets-problem-data

‘(3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99))

(define (for-each-in-powerset fn set)

(let recur ((arg-so-far ‘()) (set set))

(if (null? set)

(fn arg-so-far)

(begin

(recur arg-so-far (cdr set))

(recur (cons (car set) arg-so-far) (cdr set))))))

(define (problem-3)

(let ((total 0))

(for-each-in-powerset

(lambda (set)

(if (and (pair? set)

(pair? (cdr set))

(= (car set) (apply + (cdr set))))

(set! total (+ total 1))))

subsets-problem-data)

total))

My C Implementation

Follow Link “Download here”