[algorithm] 백준- N과 M(7)

중복 순열로 풀어야 한다.

서로 다른 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

jeongdaeun98/algorithm