BOJ 15650 : N과 M (2) - 조합 combination

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15650

 

 

N과 M(1) - 순열이 줄 세우기 문제라면, 이번 문제는 조합문제이다.

 

1 2 3 4 = 1 2 4 3 = ... = 4 3 2 1 이 모두 중복으로 취급된다.

즉, 순서가 상관이 없다.

 

그리고 사전 순으로 증가하도록 출력해야하므로,

DFS Level에서 start를 기억해두고, start에서 N까지만 list를 작성하도록 만들면 된다.

 

list에서 선택한 번호를 저장하고, 선택한 번호 + 1을 다음 DFS에 넘겨주면 된다.

이렇게 되면, 선택한 번호는 다음 DFS Level에서 선택할 수 없으므로, visit 배열이 필요가 없다.

#include <stdio.h>

int N, M;

int list[10];

void outputList()
{
	for (int i = 0; i < M;i++) printf("%d ", list[i]);
	putchar('\n');
}

void DFS(int L, int start)
{
	if (L == M)
	{
		outputList();
		return;
	}

	for (int i = start; i <= N;i++)
	{
		list[L] = i;

		DFS(L + 1, i + 1); /* 선택한 번호 보다 높은 수만 선택할 수 있도록 i + 1을 넘긴다 */
	}
}

int main(void)
{
	scanf("%d %d", &N, &M);

	DFS(0, 1);

	return 0;
}