[C++] 백준 15650번 문제풀이

순열과 조합을 정리 하려 한다.

먼저 , 순열이란 서로 다른 n개중에 r 개를 선택하는 경우의수 ( 순서 상관 있다. )

조합이란 서로 다른 n개중에서 r개를 선택하는 경우의 수 ( 순서 상관 없다 .)

#define n 4
#define r 3

1. 순열 ( 순서 O, 중복 X )

int pArr[r] = { 0, };
bool check[n + 1] = { false, }; //중복 검사

void permutation(int depth){
    if(depth == r){
        printArray(pArr);
        return;
    }
    
    for(int i = 1; i <= n; i++){
        if(!check[i]){
            check[i] = true;
            pArr[depth] = i;
            permutation(depth + 1);
            check[i] = false;
        }
    }
}

int main(void){
    cout << "순열 (순서o, 중복x)" << endl;
    permutation(0);
    
    return 0;
}

2. 중복 순열 ( 순서 O , 중복 O )

int dpArr[r] = { 0, };

void duplicatePermutation(int depth){
    if(depth == r){
        printArray(dpArr);
        return;
    }

    for(int i = 1; i <= n; i++){
        dpArr[depth] = i;
        duplicatePermutation(depth + 1);
    }
}

int main(void){
    cout << "중복 순열 (순서o, 중복o)" << endl;
    duplicatePermutation(0);

    return 0;
}

3. 조합 ( 순서 X , 중복 X )

int cArr[r] = { 0, };

void combination(int depth, int next){
    if(depth == r){
        printArray(cArr);
        return;
    }

    for(int i = next; i <= n; i++){
        cArr[depth] = i;
        combination(depth + 1, i + 1);
    }
}

int main(void){
    cout << "조합 (순서x, 중복x)" << endl;
    combination(0, 1);

    return 0;
}

4. 중복 조합 ( 순서 X, 중복 O )

int dcArr[r] = { 0, };

void duplicateCombination(int depth, int next){
    if(depth == r){
        printArray(dcArr);
        return;
    }

    for(int i = next; i <= n; i++){
        dcArr[depth] = i;
        duplicateCombination(depth + 1, i);
    }
}

int main(void){
    cout << "조합 (순서x, 중복o)" << endl;
    duplicateCombination(0, 1);

    return 0;
}