조합 생성 알고리즘

▶조합 (Combination)

---

서로 다른 n개의 원소 중에서 순서에 상관 없이 r개를 취하는 것을 

'n개에서 r개를 택하는 조합'이라고 한다. (표기 : nCr)

▶필요성

---

문제를 해결하는 과정에서 n개의 숫자 중 r개를 선택할 때

선택된 r개의 숫자들의 합이 최대/최소가 되는 경우를 찾아야 하는 경우가 있다.

불가피하게 모든 경우를 확인해보는 수밖에 없다면

어떤 소스코드를 작성해서 문제를 해결해야할까?

▶예제  : 5C3의 모든 경우를 출력하라.

---

[주어진 원소]

15, 23, 5, 1, 42

[결과]

15 23 5

15 23 1

15 23 42

15 5 1

15 5 42

15 1 42

23 5 1

23 5 42

23 1 42

5 1 42

▶Hint

---

재귀 함수로 구현하면 간단한 코드로 해결할 수 있게 된다.

주어진 원소들을 저장할 길이 5 배열과

선택된 원소들을 저장할 길이 5 배열을 만들어서 활용한다. 

[구현할 재귀 함수의 매개변수]

n : 전체 원소의 개수

r : 선택할 원소의 개수

target : 원소를 선택하는 포인터 역할

index : 선택된 원소가 저장될 인덱스

[탈출 조건]

r == 0

  :  선택하기로 한 개수만큼 모두 선택된 경우

target == n

  :  원소를 선택하는 포인터가 최대 인덱스 범위를 벗어남

target에 위치한 원소를 선택하는 경우와 선택하지 않는 경우

두 번의 함수 호출이 필요하다.

target은 함수 호출시 항상 1을 증가시켜서 인자로 넘겨야 한다.

모든 원소를 가리키며 순회하는 역할을 하는 변수이기 때문이다.

선택하는 경우엔 r을 1 감소시키고, index를 1 증가시켜 호출한다.

선택하지 않는 경우엔 r을 그대로, index도 그대로 넣고 호출한다.

index를 증가시키는 것은 현재 target이 가리키는 원소를 선택하고

다음 index에 다른 원소를 선택하기 위함이다.

index를 증가시키지 않는 것은 현재 target이 가리키는 원소를 선택하지 않고

현재 index에 다른 원소를 선택하기 위함이다.

▶소스코드

---

#include<iostream>
using namespace std;
 
int arr[5] = { 15,23,5,1,42 };
int st[5];
 
void comb(int index, int n, int r, int target) {
    if (r == 0) {
        //하나의 조합에 해당 (r개를 모두 택함)
        for (int i = 0; i < index; i++) {
            printf("%d ", st[i]);
        }
        printf("\n");
    }
    else if (target == n) {
        //tagrget이 인덱스를 초과했으므로 종료
        return;
    }
    else {
        //target 인덱스의 원소를 저장
        st[index] = arr[target];
        //해당 원소를 선택
        comb(index+1, n, r-1, target+1);
        //해당 원소를 선택하지 않음
        comb(index, n, r, target + 1);
    }
}
 
int main() {
    comb(0,5,3,0);
    return 0;
}