[Algorithm] 조합

- 순서가 상관없음

  { 1, 2, 3 }, { 1, 3, 2 }, {2, 1, 3} 다 같은 취급

 

- permutation을 쓰지 않고 재귀로 직접 구현방법

  

 5개중에 3개를 뽑는 문제의 경우

 { 1, 2, 3, 4, 5 } 가 있을 때, 3개 뽑기문제

 { 1, 2, 3 }, { 1, 2, 4 }, { 1, 2, 5 },.....{ 3, 4, 5 }

 이런식으로 진행

 특징은? 시작점을 정한 이후에는 그 전의 요소를 고려하지 않는다.

 

 즉) 이미 시작점이 1을 지나고 { 2, 3, 4 }, 이미 이런식으로 첫 번째 인덱스가 2가 되면 이 이후에 1은 절대로 뽑히지 않는다!

  

{ 1, 2, 3 } = { 2, 3, 1 } -> 이런식으로 이 둘은 같은 조합이고, { 2, 3, 1 }은 이미 시작점이 1일 때, { 1, 2, 3 }에서 나왔으므로 그 이후에는 나오지 않는다!

 

예시코드

#include <iostream>
#define MAX 5
using namespace std;

int arr[MAX];
int check[MAX];

void print(){
    for (int i = 0; i < MAX; ++i) {
        if(check[i]) cout << arr[i] << ' ';
    }
    cout << '\n';
}
void DFS(int idx, int cnt){
    if(cnt == 3){
        print();
        return;
    }
    for (int i = idx; i < MAX; ++i) {
        if(check[i]) continue;
        check[i] = true;

        DFS(i, cnt + 1);
        check[i] = false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);

    for (int i = 0; i < MAX; ++i) {
        arr[i] = i + 1;
    }
    DFS(0, 0); // idx, cnt;
    return 0;
}

 위 코드는 arr[] 배열 인자 5개중 3개를 뽑는 코드이다.

 check[] 배열에는 선택된 숫자라면 선택하지 않고, 선택하지 않은 숫자이면 체크해주는 배열이다.

 

 idx는 첫 시작 인덱스를 정하는 변수이고, cnt는 뽑고 싶은 갯수, 즉 여기서는 5개중에 3개를 뽑고싶으므로 3이될 때, 계산을 마치고 출력해주고 return해 주는 변수이다.

 

 한 마디로 cnt는 DFS내에서는 우리가 현재까지 몇개의 인자를 골랐는지 알려주는 변수이다.

 

 직접 구현해본다면 확실히 이해가 갈 수 있다!!

 

 

참조 ref) https://yabmoons.tistory.com/99