#15650 N과 M (2)

# 문제

# 입력 및 출력

# 풀이

앞의 #15649 N과 M (1)문제에서 조금 변형된 문제다

앞의 문제와 기본적인 조건은 동일하나 오름차순 수열만 출력하도록 했다

처음엔 n==0일때 visit를 관리하면 될 줄 알았는데 그건 상관없는 내용이었고

그냥 dfs인자로 현재 반복문 인덱스를 넘겨주면 됨

그럼 n+1일때 반복문은 n일때보다 더 큰값만 조회하게 됨

 

#include <iostream>
#include <vector>
using namespace std;
vector<int> p;
int visit[9];
int N, M;

void print() {
	for (int i = 0; i < p.size(); i++) {
		cout << p.at(i) << " ";
	}
	cout << "\n";
}

void dfs(int n, int k) {
	if (n == M) {
		print();
		return;
	}
	for (int i = k + 1; i <= N; i++) { // i는 앞에서 넘겨준 k값보다 1 큰 수로 설정
		if (!visit[i]) {
			p.push_back(i);
			visit[i] = 1;
			dfs(n + 1, i); // 반복문 인덱스 i를 넘겨줌
			p.pop_back();
			visit[i] = 0;
		}
	}
}

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

간단한 내용인데 은근 오래 걸렸다ㅋㅋ