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

Fie $A$~n~ $={1, 2, 3, ..., n}$. Sa se determine toate submultimile multimii $A$.

Fie mulţimea $A{~n~} = {1, 2, 3, ..., n}$. Se cere să se determine toate submulţimile mulţimii $A{~n~}$.

h2. Date de intrare

Fişierul de intrare $submultimi.in$ conţine pe prima linie numarul $N$, reprezentând numărul de elemente din mulţime.

Fişierul de intrare $submultimi.in$ conţine pe prima linie numărul natural $n$, reprezentând numărul elementelor din mulţime.

h2. Date de ieşire

Fişierul de ieşire $submultimi.out$ conţine toate submultimile submultimii $A$.

Fişierul de ieşire $submultimi.out$ conţine toate submulţimile mulţimii $A{~n~}$.

h2. Restricţii

* $1 ≤ N ≤ 16$
* Submultimile se pot afisa in orice ordine.

* $1 ≤ n ≤ 16$.
* Submulţimile se pot afişa în orice ordine.
* Submulţimea vidă nu se va afişa.

h2. Exemplu

3
|

h3. Explicaţie

h2. Indicaţii de rezolvare

...

Această problemă este o aplicaţie a 'metodei backtracking':http://en.wikipedia.org/wiki/Backtracking. 'Aici':job_detail/374752?action=view-source se găseşte o soluţie ce garantează generarea submulţimilor în ordine lexicografică.
 
Aplicaţia se mai poate rezolva şi folosind reprezentarea binară a numerelor. Recomand următorul articol ce tratează în detaliu aceste operaţii: '„Optimizarea programelor folosind operaţii pe biţi”':http://www.google.ro/url?sa=t&source=web&ct=res&cd=3&ved=0CBIQFjAC&url=http%3A%2F%2Fwww.ginfo.ro%2Frevista%2F14_5%2Ffocus.pdf&rct=j&q=opera%C5%A3ii+pe+bi%C5%A3i+cosmin+negru%C5%9Feri&ei=yqcuS7ndB5CUmAOts7yKCQ&usg=AFQjCNEkRFe0NcETCbGQYtwxtZiLl6-lIQ&sig2=u4zPps2-woQOLMdbRDyM4A. Dacă suntem la submulţimea cu indicele $idx$, dacă al $(j-1)$-lea bit din număr este $1$, atunci $j$ va face parte din submulţimea cu indexul $idx$. Iată un exemplu: dacă $idx = 5$ avem următoarea reprezentare în baza $2$ a acestui index: $5{~(2)~} = 101$. În concluzie, elementele $1$ şi $3$ fac parte din submulţimea a $5$-a. O sursă ce foloseşte această idee poate fi găsită 'aici':job_detail/374753?action=view-source.
 
O altă idee de rezolvare poate fi cea de la problema 'Combinări':problema/combinari, generându-se toate combinările de $n$ luate câte $k$, unde $k$ ia pe rând valori de la $1$ la $n$. Toate combinările de $n$ luate câte $k$ sunt de fapt toate submulţimile cu $k$ elemente. O sursă ce foloseşte această idee poate fi găsită 'aici':job_detail/374897?action=view-source.
 
Se observă că dacă sortăm submulţimile în ordine lexicografică, primele $2^n-1^$ submulţimi încep cu cifra $1$, următoarele $2^n-2^$ submulţimi încep cu cifra $2$, ... , ultima submulţime începe cu cifra $n$. Dacă se ştie numărul unei submulţimi, după ce acestea au fost sortate în ordine lexicografică, se pot afla elementele submulţimii. O sursă ce foloseşte această idee poate fi gasită 'aici':job_detail/374751?action=view-source.
 
Menţionăm în final că, indiferent de ideea de rezolvare folosită, soluţiile au complexitate exponenţială.
 
h2. Aplicaţii
 
# 'Jocul Flip':problema/flip
# 'Elimin':problema/elimin
# 'Numere3':problema/numere3
# 'Numere8':problema/numere8
# 'Sortari':problema/sortari
# 'Frac':problema/frac
# 'Ture':problema/ture
# 'Zebughil':problema/zebughil
# 'Sobo':problema/sobo
# 'Gather':problema/gather
# 'Boom':problema/boom
# 'Afacere':problema/afacere
# 'Reteta':problema/reteta

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

4381