[BOJ/백준 15665][C++] N과 M (11)

문제

https://www.acmicpc.net/problem/15665

 

문제 내용

입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열이 중복되면 안 된다.

이때 고르는 자연수는 서로 중복이어도 상관없다.

 

문제 풀이

N과 M (9)과 다르게 N과 M (11)는 수열의 원소가 중복이어도 된다는 조건이 추가되었다.

그렇기 때문에 굳이 used 배열로 사용 여부를 판단할 필요가 없다.

[BOJ/백준 15663][C++] N과 M (9)

 

코드

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

int n, m;
vector<int> arr;
vector<int> result(8, 0);

void back(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    int check_duplicate = -1;
    for (int i = 0; i < n; i++) {
        if (check_duplicate != arr[i]) {
            check_duplicate = arr[i];
            result[cnt] = arr[i];
            back(cnt + 1);
        }
    }
}

int main() {
    cin >> n >> m;
    arr.assign(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    back(0);
}