Het 2-somprobleem vraagt om, gegeven een lijst van getallen en een getal \(n\), te bepalen of er twee getallen in deze lijst zijn waarvan de som \(n\) is. Dit is een speciaal geval van het algemene subset-somprobleem, waar je gegeven een lijst van getallen moet bepalen of er een subset van deze getallen is met som \(n\). Voor het algemene subset-somprobleem is geen efficiënt algoritme gekend, maar het 2-somprobleem kan je wel heel efficiënt oplossen.
De meest eenvoudige manier om dit probleem op te lossen, is dubbel te itereren over de lijst:
for i in range(len(getallen)):
for j in range(len(getallen)):
if i != j and getallen[i] + getallen[j] == n:
return getallen[i], getallen[j]
Dit is niet heel efficiënt: in het ergste geval doe je len(getallen) * len(getallen) aantal iteraties. Stel echter dat je de getallen op voorhand sorteert:
getallen.sort()
Dan kun je door slechts één keer te itereren over de ganse lijst, het 2-somprobleem oplossen. Aangezien sorteren efficiënt is, is dit veel sneller dan de naïeve oplossing. Probeer eens na te denken hoe je dit zo efficiënt mogelijk oplost.
Schrijf een programma dat een lijst van getallen en een getal \(n\) als invoer neemt en bepaalt of er twee elementen in die lijst zijn die sommeren tot \(n\). Als dit zo is, moeten deze elementen teruggegeven worden; anders geeft het programma een lege lijst terug. Als de lijst bijvoorbeeld [2,7,11,15] is en \(n = 9\), dan is het antwoord [2, 7] omdat \(2+7=9\). Voor een lijst [3,2,4] en \(n = 1\) is het antwoord leeg omdat er geen gepaste getallen zijn.
Elk invoerbestand bestaat uit twee regels. De eerste regel geeft de lijst van getallen en de tweede regel geeft het doelwit \(n\).
Probeer jouw oplossing zo efficiënt mogelijk te maken! 🙂
Invoer:
2,7,11,15
9
Uitvoer:
(2, 7)