Sorry, weiß nicht was Devide&Conquer ist, ich würd's einfach rekursiv machen, hier mal in Python:
[tt]def sum(ls):
r=0
for i in ls:
r+=i
return r
def recurcombine(ls,target,temp,result):
if sum(temp)==target:
return [temp]
elif sum(temp)>target or ls==[]:
return []
else:
for i in range(len(ls)):
newtemp=temp[:]
newls=ls[:]
newtemp.append(newls)
del(newls[i])
result=result+recurcombine(newls,target,newtemp,[])
return result
def findcombinations(ls,sum):
r=recurcombine(ls,sum,[],[])
for i in r:
i.sort()
r.sort()
print r
i=1
while i<len(r):
if r[i-1]==r[i]:
del r[i]
else:
i+=1
return r
def main():
r=findcombinations([2, 5, 3, 8, 4, 1, 9],9)
print "Zahl der Eregebnisse: %s"%(len(r))
for i in r:
print i
main()[/tt]
Da kommt raus:
[tt]Zahl der Eregebnisse: 5
[1, 3, 5]
[1, 8]
[2, 3, 4]
[4, 5]
[9][/tt]
Edit: Shit, das Forums stellt die Einrückung nicht ordentlich da...
28.04.2024, 10:00
Sprache ändern
Registrieren
Anmelden
