Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTPODZB - Podzbiory

Napisz program wyznaczający wszystkie podzbiory k-elementowe zbioru {1,...,n}.

Wejście

W pierwszej linii liczba testów t. W każdym z kolejnych t wierszy znajdują się dwie liczby n k, gdzie 0 < k ≤ n < 20 .

Wyjście

Dla każdego testu w oddzielnych liniach wszystkie możliwe k elementowe podzbiory zbioru {1,...,n}. Zbiory powinny być podane w kolejności leksykograficznej, każdy zbiór w jednej linii, liczby w kolejności od najmniejszej do największej. Po ostatnim zbiorze w teście pusta linia.

Przykład

Wejście:
2
3 3
5 2
Wyjście:
1 2 3

1 2
1 3 
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5 

Wskazówka

Posłuż się następującą formułą rekurencyjną:
Funkcja podzb(T,rozmT,k,A,rozmA) ma wypisać wszystkie zbiory A U X, gdzie X jest k-elementowym podzbiorem T (inicjalnie A jest pusty i rozmA=0).

  • jeśli k=0 wypisz A;
  • jeśli k=rozmT wypisz A, wypisz T;
  • w pozostałych przypadkach wykonaj funkcje
    podzb({T[1],T[2],...,T[rozmT-1]},rozmT-1,k-1,A U T[0],rozmA+1) oraz
    podzb({T[1],T[2],...,T[rozmT-1]},rozmT-1,k,A,rozmA).

Dodane przez:kuszi
Data dodania:2006-01-22
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.