[C/C++] 백준 15652번 - N과 M (4) (DFS, 백트래킹)

 

 

<코드>

#include<iostream>
using namespace std;

int memo[9];
int N, M;

void recursion(int x, int pre)
{
	if (x == M + 1)
	{
		for (int i = 1; i <= M; i++)
			cout << memo[i] << " ";
		cout << "\n";
	}
	else
	{
		for (int i = 1; i <= N; i++)
		{
			if (pre <= i)
			{
				memo[x] = i;
				recursion(x + 1, i);
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	recursion(1, 0);
}

 

배열에서 방문 표시를 안 하되 비 내림차순으로 표시하기 위해 재귀로 넘어오기 전 값(pre)과 현재 값을 비교하여 수열을 출력하였다.

 

 

 

www.acmicpc.net/problem/15652

15652번: N과 M (4)