(백준 c++)15649 N과 M(1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

next_permutation() 함수와 reverse() 함수를 이용해 nPr 순열을 구현.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int dfs(vector<int>& v, int M)
{
	reverse(v.begin() + M, v.end());
	return next_permutation(v.begin(), v.end());
}

int main() {
	int N, M;
	vector<int> v;
	
	scanf("%d %d", &N, &M);
	
	for(int i = 1; i <= N; i++)
		v.push_back(i);
		
	while(1)
	{
		for(int i = 0; i < M; i++)
			printf("%d ", v[i]);
		printf("\n");
		
		if(!dfs(v, M))
			break;
	}
	return 0;
}