조합은 어떻게 코드로 구현할 수 있을까?
조합은 순열과 다르게 중복된 수는 뽑을 수 없으므로 방문한 숫자에 대하여 방문 처리 벡터를 만들고, 이미 방문 처리한 숫자에 대해서는 가지치기(punning)을 해주면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void combi(vector<int> &v, vector<bool> &vis, int n, int m, int depth){
if(depth == m){
for(int i = 0; i < m; i++){
cout << v[i] << " ";
}
cout << "\n";
return;
}
for(int i = 1; i <= n; i++){
if(vis[i]){
continue;
}
vis[i]= true;
v.push_back(i);
combi(v, vis, n, m, depth+1);
//부모 노드 상태로 되돌려주기
vis[i]= false;
v.pop_back();
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m;
vector<int> v;
cin >> n >> m;
vector<bool> vis(n, false); //방문 표시 벡터
combi(v, vis, n, m, 0);
}