BOJ - 15651번_N과 M (3)

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

  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.
  • 같은 수를 여러 번 골라도 된다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

백트래킹을 이용한다.

이전 문제들(N과 M 시리즈)과 풀이 방식은 동일하지만 중복이 가능하므로 check 하는 부분만 제거해준다.


소스코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[10];

void func(int num) {
	if(num==M) {
		for(int i=0; i<M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for(int i=1; i<=N; i++) {
		arr[num] = i;
		func(num+1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	func(0);
}