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.

Opgave

Ontwerp en implementeer hiervoor een algoritme dat gebruik maakt van backtracking. Schrijf een Python-functie subsetSom(rij: list, k: int) die een rij van getallen en een getal k als argumenten neemt. De functie moet een lijst van indices teruggeven waarbij de som van de getallen horende bij de indices gelijk is aan $k$.

Voorbeelden

                
            >>> subsetSom([12, 10, 2, 7, 4], 11)
[3, 4]
>>> subsetSom([15, 12, 3, 8, 7], 9)
[]
>>> subsetSom([15, 12, 3, 7, 7], 12)
[1]