조합 활용하기

 

예제 입력 1

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 3

0

예제 출력 1

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

 

- 조합에서 STL 없이 next_permutation 안쓰는게 나을 듯

#include <stdio.h>
#define MAX_SIZE (14)

void DFS(int* num, bool* visited, int start, int N, int r)
{
	if (r == 0)
	{
		for (int i = 0; i < N; i++)
		{
			if (visited[i]) printf("%d ", num[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i < N; i++)
	{
		visited[i] = true;
		DFS(num, visited, i + 1, N, r - 1);
		visited[i] = false;
	}
}

int main(void)
{
	while (true)
	{
		int N;

		int num[MAX_SIZE];
		bool visited[MAX_SIZE];

		scanf("%d", &N);

		if (N == 0) return 0;

		for (register int i = 0; i < N; i++)
		{
			scanf("%d", &num[i]);
			visited[i] = false;
		}

		DFS(num, visited, 0, N, 6);
		printf("\n");
	}

	return 0;
}