728x90
반응형
중복 조합으로 풀어야한다!
서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것,
중복이 허용된다.
조합과 차이점
중복을 허용하므로 값을 추가했을 때 index에 1을 더하지 않는다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void overlapCombination(int target, int index, vector<int> realVector, vector<int> numVector){
if(target == 0){
for(int i = 0; i < numVector.size(); i++){
cout << numVector[i] << " ";
}
cout << "\n";
return;
}
if(index == realVector.size()){
return;
}
numVector.push_back(realVector[index]);
overlapCombination(target - 1, index, realVector, numVector);
numVector.pop_back();
overlapCombination(target, index + 1, realVector, numVector);
}
int main(void){
int count,target, num;
cin >> count >> target;
vector<int> realVector, numVector;
for(int i = 0; i < count ; i++){
cin >> num;
realVector.push_back(num);
}
sort(realVector.begin(), realVector.end());
overlapCombination(target, 0, realVector, numVector);
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102807.cpp
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - N과 M(9) (0) | 2020.10.30 |
---|---|
[algorithm] 백준 - ABCDE (0) | 2020.10.29 |
[algorithm] 백준- N과 M(7) (0) | 2020.10.29 |
[algorithm] 백준 - 모든 순열 (0) | 2020.10.29 |
[algorithm] 백준 - 이전 순열 (0) | 2020.10.29 |