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 este o aplicatie a metodei backtracking. Aceasta 'solutie':job_detail/374752?action=view-source garanteaza generarea submultimilor in ordine lexicografica.
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.
Problema se mai poate rezolva si folosind reprezentarea binara a numerelor. Daca suntem la submultimea $i$ si daca al $j-1$-lea bit din numar este $1$ atunci $j$ va face parte din submultimea $i$. Exemplu: daca $i=5$, $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.
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$. Toate combinarile de $n$ luate cate $k$ sunt de fapt toate submultimile cu k elemente. 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.
