로또

시간 제한1초메모리 제한128 MB

요약

오름차순으로 주어진 k개 수의 집합마다 6개를 고르는 모든 조합을 사전순으로 출력하고, 테스트 사이에 빈 줄을 넣습니다.

난이도: 보통10점 중 4점
유형: 백트래킹, 재귀, 조합론
정답자: 아직 제출이 없습니다

문제

독일 로또는 $\{1, 2, \ldots, 49\}$ 에서 서로 다른 수 6개를 고르는 방식으로 진행된다.

로또 번호를 고를 때 널리 쓰이는 전략 하나는, 49개의 수 중에서 $k$ 개( $k > 6$ )를 미리 골라 집합 $S$ 를 만든 뒤, 그 $S$ 안의 수만으로 6개를 선택하는 것이다.

예를 들어 $k = 8$ , $S = \{1, 2, 3, 5, 8, 13, 21, 34\}$ 라면, 이 집합에서 6개를 고르는 경우의 수는 모두 28가지이다.

집합 $S$ 와 $k$ 가 주어졌을 때, $S$ 에서 6개를 고르는 모든 방법을 출력하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 주어진다. 줄의 첫 번째 수는 $k$ ( $6 < k < 13$ )이고, 이어지는 $k$ 개의 수가 집합 $S$ 의 원소이다. $S$ 의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 $S$ 에서 6개를 고르는 모든 방법을 사전순으로 출력한다. 한 방법은 고른 6개의 수를 오름차순으로, 공백으로 구분하여 한 줄에 출력한다.

서로 다른 테스트 케이스의 출력 사이에는 빈 줄을 하나 출력한다.

예제3

예제 1

입력

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예상 출력

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

예제 2

입력

7 1 2 3 4 5 6 7
0

예상 출력

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

예제 3

입력

8 1 2 3 5 8 13 21 34
0

예상 출력

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34