Rezolvare PBinfo #3952

Cerința

Fie n un număr natural nenul, mulțimea A={1,2,3,...,n} și un număr m, 1 ≤ m ≤ n. Să se determine toate partițiile disjuncte ale mulțimii A, formate din submulțimi cu exact m elemente.

O partiție a mulțimii A este formată din k (1 ≤ k ≤ n) submulțimi disjuncte ale lui A: A1, A2, …, Ak cu proprietatea că A=A1U A2 U...U Ak.

Date de intrare

Fișierul de intrare partitiimultime3.in conține pe prima linie numerele n și m.

Date de ieșire

Fișierul de ieșire partitiimultime3.out va conține câte o linie pentru fiecare partiție determinată. Submulțimile vor fi separate în fiecare linie cu ajutorul caracterului *, iar elementele fiecărei submulțimi se vor scrie fără spațiere, ca în exemplul de mai jos. Dacă problema nu are soluții, atunci se va afișa IMPOSIBIL.

Restricții și precizări

• 1 ≤ m ≤ n ≤ 9
• Partițiile determinate se vor afișa în ordine lexicografică a indicelui submulțimii în care se pun elementele. De exemplu soluția 16*24*35* este afișată înaintea soluției 15*26*34* deoarece 1,2,3,2,3,1 este înaintea lui 1,2,3,3,1,2.

Exemplu:

partitiimultime3.in

4 2

partitiimultime3.out

12*34*
13*24*
14*23*

Explicație

Există 3 partiții formate din submulțimi cu exact 2 elemente: {1,2} U {3,4} , {1,3} U {2,4} , {1,4} U {2,3}.