조합론

조합도 순열과 같은 느낌으로 풀면 되는데 조합의 특징만 살려주면 된다
 
조합은 순열과 다르게 순서가 상관이 없다
 
즉 1 2 3 이랑 2 1 3이랑은 같다.
 
따라서 오름차순으로 조합들을 출력한다 할때
N을 base로 출력했으면 그 다음부터는 N이 없다고 생각해도 된다.
 

왜냐하면 N을 base로 생각하고 나온 조합들이 N이 들어간 모든 조합들이기 때문이다.
 
따라서 순열 DFS코드를 조금만 변형해주면 된다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 10

using namespace std;

int arr[SIZE];
vector<int> ans;

int N, M;

void print() {
	for (int i = 0; i < M; i++) cout << ans[i] << " ";
	cout << "\n";
}

void DFS(int start, int cnt) {
	if (cnt == M) {
		print();
		return;
	}

	for (int i = start; i <= N; i++) {
		ans.push_back(arr[i]);
		DFS(i + 1, cnt + 1);
		ans.pop_back();
	}
	return;
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) arr[i] = i;
	DFS(1, 0);
	return 0;
}

 
매개변수로 start를 추가하여 start 앞 원소들은 이미 count한 것들이므로 빼면 된다
참고로 이 start변수가 있으니 visited는 따로 필요가 없다.