[BOJ/15650/C++] N과 M(2)

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다.

조건

• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

SOL

N개 중에서 M개를 고르는 조합의 "수"를 물어보는 문제입니다. 조합을 구현할 수 있다면, 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int n, r;

void printV(vector<int> v)
{
  for (int i = 0; i < v.size(); i++)
  {
    cout << v[i] + 1 << " ";
  }
  cout << '\n';
}
void makeCombination(vector<int> v, int start)
{
  // 종료조건
  if (v.size() == r)
  {
    printV(v);
    return;
  }
  for (int i = start + 1; i < n; i++)
  {
    v.push_back(i);
    makeCombination(v, i);
    v.pop_back();
  }
}

int main()
{
  cin >> n >> r;
  vector<int> vec;
  makeCombination(vec, -1);
  return 0;
}