[ C / C++ ] 백준 15664 N과 M(10)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

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

bool check[8]; 
int n, m, num[8], result[8];

void getResult(int count, int start) {

    if (count == m) {
        for (int i = 0; i < m; i++)
            cout << result[i] << ' ';
        cout << '\n';
        return;
    }
    int prev_num = -1; 

    for (int i = start; i < n; i++) {
        if (!check[i] && prev_num != num[i]) {
            check[i] = true;
            result[count] = num[i];
            prev_num = num[i];

            getResult(count + 1, i);
            check[i] = false;
        }
    }
}

int main(void) {

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> num[i];

    sort(num, num + n);

    getResult(0, 0);
    return 0;
}