BOJ 15652 : N과 M (4) - 중복 조합 combinations with repetition

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15652

 

중복 순열에서 순서가 의미가 없다면, 중복 조합이 된다.

 

중복으로 선택은 가능하되, 다음으로 선택해야할 숫자가 작아서는 안되므로, 

DFS에 현재 선택한 값을 그대로 넘겨주면, 다음 Level에서는 작은 값을 선택할 수 없게 된다.

#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);
	}
}

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

	DFS(0, 1);

	return 0;
}