부분집합의 합

#include <stdio.h> 

// 부분집합 출력. 

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

    int i; 

    static int c=0;

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

    if(n==0) return;

    printf("%d :: {", ++c); 

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

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

    printf("%d}\n",set[n-1]); 

} 

// value는 값들, subset는 지금까지 선택한 값들, n은 전체 값의 갯수

// k는 현재 고려할 값의 위치

// m은 지금까지 선택한 값의 갯수

// sum은 남아 있는 합

void psum(int value[], int subset[], int n, int k, int m, int sum) {

    // sum이 0이 되었다면 순환호출을 멈춘고 출력을 해준다.

    if (sum==0) {

        print_subset(subset, m);

        return ; 

    }

    // 만약 모든 위치를 고려했거나, 현재 값이 sum보다 크다면 끝낸다.

    if(k>=n || value[k]>sum) return;

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

    subset[m] = value[k]; 

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

    psum(value, subset, n, k+1, m+1, sum-value[k]); 

    // k번째 원소를 선택하지 않았다. .

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

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

    psum(value, subset, n, k+1, m, sum); 

} 

int main() { 

    // subset는 값을 뽑아넣은 부분집합이다.

    int value[30]={5, 10, 12, 13, 15, 18,};

    int subset[30]={0,};

    int i, n, r; 

    // 6은 주어진 값의 갯수이다. 0은 다음에 고려해야 할 위치

    // 다음 0은 현재 까지 subset에 들어간 갯수, 30은 합이다.

    psum(value, subset, 6, 0, 0, 30);

    return 0;

}