combination 조합

#include <stdio.h> 

// 부분집합 출력. 

void print_subset(int set[], int n) { 

    int i; 

    // 부분집합의 원소 출력. 

    for (i = 0; i < n; i++) 

        printf("%d ", set[i]); 

    printf("\n"); 

} 

// c(n,r)=c(n-1,r-1)+c(n-1,r) 을 이용한 부분집합 구하기 

// subset는 구해진 부분집합

// n은 집합의 크기, k는 현재 고려가 되는 set의 원소 (값은 k+1)

// m은 구해야할 부분집합의 크기

// r은 현재까지 구한 부분집합의 갯수

void comb(int subset[], int n, int k, int m, int r) {

 // 만약 남아있는 원소의 갯수가 구해야할 원소보다 작거나

    if (n-k<m-r) return; 

 // 혹은 이미 모든 원소를 다 선택했다면 순환호출을 멈춘다.

 // 모든 원소를 다 구했을 경우 즉 r==m일 때만 출력을 해준다. 

    if (r==m) {

        print_subset(subset, m);

        return ; 

    } 

 // 만약 앞으로 더 구해야할 원소가 남았고, 또 가능하다면

 // k번째 원소를 선택한 경우와 선택하지 않은 두가지 경우를 각각

 // 순환호출로 돌려준다.

// subset의 r번째 원소로 k번째 set의 원소를 넣어 준다.

    subset[r] = k+1; 

// 지금까지 선택한 원소가 r개 였고, 지금 1개 선택했으므로 r+1개를 선택하였다.

    comb(subset, n, k+1, m, r+1); 

// k번째 원소를 선택하지 않았다. 여전히 r개를 가지고 호출을 한다.

// 위에서 넣었던 r번째 원소는 다음 순환호출 때 다른 값이 들어 가기 때문에

// 걱정하지 않아도 좋다.

    comb(subset, n, k+1, m, r); 

} 

int main() { 

 // subset는 r개의 원소를 뽑아넣은 부분집합이다.

    int subset[32]={0,};

    int i, n, r; 

 // set의 크기를 입력받는다. 원소는 1부터 n까지 이다.

    printf("최대값 : "); 

    scanf("%d", &n);

 // 부분집합의 원소의 갯수를 입력받는다.

    printf("원소개수 : "); 

    scanf("%d", &r); 

 // 부분집합 subset, 집합의 크기 n, 시작위치 0, 

 // 구해야할 부분집합의 크기 r, 지금까지 구한 부분집합의 갯수 0

 // 으로 combination (조합) 함수 comb를 호출해 준다.

    comb(subset, n, 0, r, 0); 

    return 0;

}