# From a list of numbers find all the combinations that sum to more than a given number

Staff Emeritus
This is born out of musings around coalition governments that arise from the party with the most votes not achieving ≥50% of the votes (as opposed to emergency coalitions).

Taking the figures below how would one go about determining all the possible combinations of parties who combined have >50% of the votes without sitting down and working them out one by one?

Kid gloves please I haven't studied maths for the better part of a decade...

Parties / Percentage of votes

Pink / 21
Orange / 19
Brown / 16
Blue / 10
Green / 10
Tan / 8
Red / 5
Black / 4
Purple / 4
White / 3

## Answers and Replies

Brute force my friend !
Here is a groovy script that answers your question:
Code:
def X=[Pink:21, Orange:19, Brown:16, Blue:10, Green:10, Tan:8, Red:5, Black:4, Purple:4, White:3]
def XS=X.keySet() as List
def N=XS.size()
def F; F={ ix,n ->
def L0=[XS[ix]]
if(n==1) return [L0]
def L=[]
for(def j=ix; j<N-1; j++) {
F(j+1, n-1).each{ L<<(L0+it) }
}
L
}
def OK=[:]
for(def i=0;i<N;i++) {
for(def j=1;j<=N-i;j++) {
def c=F(i,j)
c.each{
def s=0; it.each { s+=X[it]}
if(s>50) OK[it]=s
}
}
}
OK.keySet().sort{x,y->OK[y]<=>OK[x]}.each{ println "$it:${OK[it]}%" }
I don't post the result since there are 502 winning combinations going all the way from 51% up to 100%

Staff Emeritus