(작성중) [알고리즘] 조합 시리즈

Sujung Shin·2023년 5월 4일
0

조합은 어떻게 코드로 구현할 수 있을까?
조합은 순열과 다르게 중복된 수는 뽑을 수 없으므로 방문한 숫자에 대하여 방문 처리 벡터를 만들고, 이미 방문 처리한 숫자에 대해서는 가지치기(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);
}
profile
백문이불여일타

0개의 댓글

관련 채용 정보