Combinații cu suma dată
Un automat de cafea trebuie să dea rest 7 lei și are monede de 2, 3, 6 și 7 lei, din fiecare câte vrei. În câte feluri poate da restul? Problema combină tot ce ai învățat la backtracking: pornești de la un indice ca să eviți duplicatele, dar poți refolosi același element și te oprești de îndată ce suma depășește ținta.
Problema
Primești o listă de numere pozitive distincte (candidati) și o tinta. Vrei toate combinațiile (fără să conteze ordinea) a căror sumă este exact ținta. Același număr poate fi folosit de oricâte ori.
Scrie funcția combinatii_suma(candidati, tinta) care returnează toate combinațiile cu suma tinta, fiecare cu elementele în ordine crescătoare, folosind backtracking. Un candidat poate fi folosit de mai multe ori. Sortează candidații la înce…
- Sortează candidații și scrie backtrack(start, ramas).
- Dacă ramas == 0 salvezi o copie; în buclă, break dacă candidati[i] > ramas.
- Apel recursiv backtrack(i, ramas - candidati[i]). Trebuie să apară: [[2, 2, 3], [7]], [[2, 2, 2, 2], [2, 3, 3], [3, 5]], [], [[1, 1, 1]].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan