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

중복 조합으로 풀어야한다!

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

jeongdaeun98/algorithm