BOJ 15664 · N과 M (10)

알고리즘 분류 : 브루트 포스  

입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (6) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복을 제거하는 방법은 N과 M (9) 문제와 동일하게 처리하면 된다.

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

int n, m;
bool check[8];
int a[8];
vector<int> v;
set<vector<int>> s;

void solve(int cnt, int idx) {
    if (cnt == m) {
        s.insert(v);
        return;
    }
    for (int i=idx; i<n; i++) {
        if (!check[i]) {
            check[i] = true;
            v.push_back(a[i]);
            solve(cnt+1, i);
            v.pop_back();
            check[i] = false;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    solve(0, 0);
    for (auto k : s) {
        for (auto t : k) printf("%d ", t);
        printf("\n");
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin, stdout
from itertools import combinations
input = stdin.readline
print = stdout.write

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
for k in sorted(set(combinations(a, m))):
    print(' '.join(map(str, k))+'\n')

---

참고

• 백준 온라인 저지 : BOJ 15664
• N과 M (6)
• N과 M (9)