반응형
아이디어
그냥 백트랙킹... 중복 없애고... 중복 조합....
풀이
수열을 입력받고 오름차순으로 정렬한 뒤에 중복된 항목을 제거한다.
백트랙킹을 통해 중본 조합을 구한다.
출력한다. 끝.
코드
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"
int N, M;
vector<int> arr, ret;
vector<vector<int>> ans;
void dfs(int cursor) {
if (ret.size() == M) {
ans.push_back(ret);
return;
}
for(int i = cursor; i < N; ++i) {
ret.push_back(arr[i]);
dfs(i);
ret.pop_back();
}
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
FAST_IO;
cin >> N >> M;
arr = vector<int>(N);
FOR(i, N)
cin >> arr[i];
sort(arr.begin(), arr.end());
int i = 1;
while (true) {
if (i >= arr.size()) break;
if (arr[i] == arr[i - 1]) arr.erase(arr.begin() + i);
else ++i;
}
N = arr.size();
dfs(0);
for (auto& el : ans) {
for (auto& num : el)
cout << num << " ";
cout << EL;
}
return 0;
}
반응형
'프로그래밍 > PS' 카테고리의 다른 글
[C++] 백준 11660번: 구간 합 구하기 5 (0) | 2020.12.07 |
---|---|
[C++] 백준 1021번: 회전하는 큐 (0) | 2020.12.04 |
[C++] 백준 1010번: 다리 놓기 (0) | 2020.11.28 |
[C++] 백준 1934: 최소공배수 (0) | 2020.11.28 |
[C++] 백준 1026번: 보물 (0) | 2020.11.28 |