[c++/백준] 15650 N과 M(2)

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

N과 M(1)에서 조건만 조금 추가하면 해결 가능하다.

 

N과 M(1)이 중복도 허용하는 순열이라면 이 문제는 중복을 허용하지 않는 조합과 같은 문제라고 생각하면 된다. 

출력되는 모든 숫자는 첫번째 숫자는 두번째 숫자보다 작도록, 두번째 숫자는 세번째 숫자보다 작도록 하면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

int arr[9] = {};
bool visited[9] = { false };
int n, m;

void dfs(int depth, int x) {
	if (x == m) {
		for (int i = 0; i < m; i++) {
			cout << arr[i] << " ";
		}
		cout << '\n';
		return;
	}
	for (int i = depth; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			arr[x] = i;
			dfs(i + 1, x + 1);
			visited[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	dfs(1,0);
}