백준 N과M(1)

N과M 문제집은 순열과 조합등의 기본 지식을 연습해 볼 수 있는 좋은 예제가 된다.

N과M(1) 문제는 nCm 조합문제이다.

N개의 수열중에서 M개를 선택했을하는 수열을 구하는 문제이다.

간단한 재귀문으로 구현이 가능하다.

구현시 bool sel[8]; 코드를 이용하여 자기자신을 선택한 상태이면 고르지 않는 과정을 넣어주어야한다.

11, 22, 33, 44 등의 자기 수가 연달아서 삽입되는 것을 막아준다.

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

  int N, M;
  int arr[8];
  vector<int> v;
  bool sel[8];
  void solve(int idx, int cnt){
    if(cnt == M){
      for(int i=0;i<M;i++){
        cout << v[i] << " ";
      }
      cout << '\n';
      return;
    }
    for(int i=idx;i<N;i++){
      if(sel[i] == true) continue;
      sel[i] = true;
      v.push_back(arr[i]);
      solve(idx, cnt+1);
      sel[i] = false;
      v.pop_back();

    }
  }
  int main(){
    cin >> N >> M;
    for(int i=1;i<=N;i++){
      arr[i-1] = i;
    }
    solve(0, 0);
  }