## 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.

Pages: 1 2

### 7 Responses to “Subset Sums”

1. […] 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 […]

```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]
```
3. turuthok said

For the 2^10:

```n = 2**10
f =  * n
f, f = 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

4. turuthok said

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.

5. Christopher Oliver said

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))

6. Khanh Nguyen said
```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]
```