3
|

h3. Explicaţie

h2. Indicaţii de rezolvare
 
Problema este o aplicatie a metodei backtracking. O solutie de 100 de puncte poate fi gasita 'aici':job_detail/374752?action=view-source.
 
Problema se mai poate rezolva si folosind reprezentarea binara a numerelor, daca al $i-1$-lea bit din numar este $1$ atunci $i$ va face parte din acea submultime. Exemplu: $5{~(2)~}=101$ deci elementele $1$ si $3$ fac parte din submultimea a $5$-a. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374753?action=view-source.
 
O alta idee de rezolvare poate fi cea de la problema 'combinari':problema/combinari, generandu-se toate combinarile de $n$ luate cate $k$, unde $k$ ia pe rand valori de la $1$ la $n$. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374897?action=view-source.
 
Se observa ca daca sortam submultimile in ordine lexicografica, primele $2^n-1^$ submultimi incep cu cifra $1$, urmatoarele $2^n-2^$ submultimi incep cu cifra $2$, ... , ultima submultime incepe cu cifra $n$. Daca se stie numarul unei submultimi, dupa ce acestea au fost sortate in ordine lexicografica, se pot afla elementele submultimii. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374751?action=view-source.

...

== include(page="template/taskfooter" task_id="submultimi") ==