Gegeven is een rij van natuurlijke getallen \((a_1,...,a_n)\) en een natuurlijk getal \(k\). Gevraagd is te controleren of het getal \(k\) kan gevormd worden als de som van getallen uit de rij \((a_1,...,a_n)\). Hierbij mag elk getal uit de rij maar hoogstens eenmaal gebruikt worden.

Stel dat we de rij (4, 5, 3, 8, 2, 9) gegeven hebben. We kunnen het getal 15 dan bijvoorbeeld vormen als \(5 + 8 + 2\). Merk op dat de oplossing echter niet altijd uniek is: hier vormt bijvoorbeeld ook \(4 + 3 + 8\) het getal 15.

Om deze oefening op te lossen, implementeer je de gegeven interface SubsetSum¹ in een klasse RecursiveSubsetSum. Schrijf hiervoor een methode public List<Boolean> subsetSum(List<Integer> list, int sum), die als invoer de rij getallen en de te vormen som krijgt. Het algoritme geeft een selectie van getallen uit de invoerrij terug die sommeren tot het te vormen getal. Hierbij betekent een waarde true op index \(i\) in de teruggegeven rij dat je het getal op index \(i\) in gegeven rij gebruikt in de som (en vice versa). Indien er geen oplossing bestaat, geeft deze methode null terug.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Hierin zijn enkele kleine testgevallen opgenomen met een unieke oplossing. Je kan hierin zelf ook eenvoudig extra testgevallen toevoegen.