N 과 M 3

문제 링크

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 같은 숫자를 여러번 골라도 된다.

이 문제는 진짜 완전탐색인데 왜 백트래킹인지 잘 모르겠다. 기존에 작성한 제약 조건을 모두 삭제하여 해결 할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ch/*숫자 사용 여부*/, arr/*완성된 수열*/;
int n, m;
void r(int p) {
	if(p > m) { // 끝까지 탐색한 경우
		for(int i=1;i<=m;i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
		return; // 지금까지 저장된 문자열 출력하고 탐색 종료
	}
	for(int i=1;i<=n;i++) {				
		arr[p] = i; // 현재 위치에 i라는 숫자 사용
		r(p + 1); // 다음 위치 탐색		
	}
}
int main() {
	cin >> n >> m;
	ch = vector<int>(n + 1); arr = vector<int>(m + 1);
	r(1);
	return 0;
}