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

이 문제는 dfs이다.

이 문제는 N과 M(6)과 N과 M(9)와 연관된 문제이다.

중복되는 수열을 여러번 출력하면 안되며,
수열은 중복된 수로 나열되어있을 수 있다.

포인트는

'N과 M(6) + 재귀 시 중복된 수가 있는지 확인'

이다.

N과 M(6)은 조합문제이다.

조합 코드는 두 가지가 있는데,

void combination(int target, int index, vector<int> realVector, vector<int> numVector){
    if(target == 0){
        sort(numVector.begin(), numVector.end());
        combinationVector.push_back(numVector);
        return;
    }
    if(index == realVector.size()){
        return;
    }
    numVector.push_back(realVector[index]);
    combination(target - 1, index + 1, realVector, numVector);
    numVector.pop_back();
    combination(target, index + 1, realVector, numVector);
}

하나는 index로 반복해서 굳이 for문과 방문여부를 체크하지 않아도 되고,

void combination(int target, int index, vector<int> realNumVector,vector<int> numVector){
    if(target == 0){
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i = index; i < realNumVector.size(); i++){
        if(selected[i]) continue;
        numVector.push_back(realNumVector[i]);
        selected[i] = true;
        combination(target - 1, i, realNumVector, numVector);
        selected[i] = false;
        numVector.pop_back();
    }
}

두번째는 for문과 방문여부를 체크해야한다.

N과 M(9)처럼 재귀 시 중복된 수가 있는지 확인하면 된다.
나는 for문으로 이루어진 조합코드를 활용했다.

//백준 N과 M (10)
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int selected[8] = {false};
void combination(int target, int index, vector<int> realNumVector, vector<int> numVector){
    if(target == 0){
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i] << " ";
        }
        cout << "\n";
        return;
    }
    int beforeNum = -1;
    for(int i = index; i < realNumVector.size(); i++){
        if(selected[i] || beforeNum == realNumVector[i]) continue;
        selected[i] = true;
        beforeNum = realNumVector[i];
        numVector.push_back(realNumVector[i]);
        combination(target - 1, i, realNumVector, numVector);
        numVector.pop_back();
        selected[i] = false;
    }
}
int main(void){
    int count, target, num;
    cin >> count >> target;
    vector<int> realNumVector, numVector;
    for(int i = 0; i < count; i++){
        cin >> num;
        realNumVector.push_back(num);
    }
    sort(realNumVector.begin(), realNumVector.end());
    combination(target, 0, realNumVector, numVector);
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102902.cpp

jeongdaeun98/algorithm