[BOJ/15656/C++] N과 M (7)

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

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

조건

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

풀이

N개 중에 M개를 고르는데, 같은 수를 여러번 골라도 되는 문제이다. 즉, [1,2,3,4] 가 있다면, [1,1],[2,2]와 같은 조합이 나올 수 있다.

Goal : 선택된 M개의 수열
if(x==M) 이면 종료
Choice(매번 선택) : 뽑는 숫자의 갯수
func(x)형태로, x로 몇개를 뽑았는지 기억하자.

제약조건: 중복된 숫자도 골라도됨.
반복을 돌 때, 앞에꺼도 같이 돌자. 시작을 0으로하면 됨.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, M;
int arr[10];

int permu[10];

void printV()
{
  for (int i = 0; i < M; i++)
  {
    cout << arr[permu[i]] << " ";
  }
  cout << '\n';
}
void make_permutation(int x)
{
  if (x == M)
  {
    printV();
    return;
  }

  for (int i = 0; i < N; i++)
  {
    permu[x] = i;
    make_permutation(x + 1);
  }
}

int main()
{
  fastio;
  cin >> N >> M;
  for (int i = 0; i < N; i++)
  {
    cin >> arr[i];
  }
  sort(arr, arr + N);
  make_permutation(0);
  return 0;
}