728x90
반응형
중복 순열로 풀어야 한다.
서로 다른 n개의 원소에서 r개를 뽑아 한줄로 세우는 경우의 수,
중복도 허용되어 같은 원소를 r개 뽑을 수 있다.
순열과 차이점
중복을 허용하므로 반복문을 도는데 초깃값을 0으로 설정한다.
재귀함수이고, 반복문을 돌며 vector에 값을 추가한다.
값을 반환 후 vector에서 원소를 삭제한다.
순열은 반복문을 돌며 swap하는 특징이 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void overlapPermutation(int index, vector<int> numVector, vector<int> realVector, int target){
if(target == index){
for(int i = 0 ; i < numVector.size(); i++){
cout << numVector[i] << " ";
}
cout << "\n";
return;
}
for(int i = 0; i < realVector.size(); i++){
numVector.push_back(realVector[i]);
overlapPermutation(index + 1, numVector, realVector, target);
numVector.pop_back();
}
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int count, target, num;
cin >> count >> target;
vector<int> realNumVector;
for(int i = 0; i < count; i++){
cin >> num;
realNumVector.push_back(num);
}
sort(realNumVector.begin(), realNumVector.end());
vector<int> numVector;
overlapPermutation(0,numVector, realNumVector, target);
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102806.cpp
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - ABCDE (0) | 2020.10.29 |
---|---|
[algorithm] 백준 - N과 M (8) (0) | 2020.10.29 |
[algorithm] 백준 - 모든 순열 (0) | 2020.10.29 |
[algorithm] 백준 - 이전 순열 (0) | 2020.10.29 |
[algorithm] 숨바꼭질 3 (0) | 2020.10.29 |