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 210. 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.
Programming Praxis 
[…] 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):
import Data.List greplin3 :: [Integer] -> Int greplin3 = length . filter (\s -> sum (init s) == last s) . tail . subsequences main :: IO () main = print $ greplin3 [ 3, 4, 9,14,15,19,28,37,47,50,54 ,56,59,61,70,73,78,81,92,95,97,99]For the 2^10:
n = 2**10 f = [1] * n f[0], f[1] = 0, 0 p = [] for i in xrange(2, n): if f[i]: for j in xrange(i+i, n, i): f[j] = False p.append(i) m = {} def go(idx, sum): if sum >= n: return 0 if idx >= len(p): return f[sum] if (idx, sum) in m: return m[(idx, sum)]; r = go(idx+1, sum) + go(idx+1, sum+p[idx]) m[(idx, sum)] = r return r print go(0, 0) - len(p)~/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))
let power_set (list:int list) = let rec helper l result = match l with | [] -> result | x::xs -> let ll = List.map (fun s -> x::s) result helper xs (List.append result ll) helper list [[]] let subset_sums (list:int list) = power_set list |> List.tail //the first set is the empty set |> List.filter (fun x -> List.head x = (List.tail x |> List.sum)) |> List.length subset_sums [3;4;9;14;15;19;28;37;47;50;54;56;59;61;70;73;78;81;92;95;97;99]My C Implementation
Follow Link “Download here”