judge3-3.c

#include <stdio.h>
int weight,result = 0;//result 紀錄是否有解，為 0 則無解，為 1 則有解
/*
 * combination function:
 * s array記錄所有砝碼的重量
 * m 表示砝碼的個數
 * n 想要取的砝碼個數
 */
void combination(int *s, int m, int n, int pos, int got) {
    int i, tmp, sum;
    if (n == got) {
        /*
         * 當完成組合後，需先把砝碼相加取出總重量
         * 再判斷是否與要求的克數相同，如符合則印出
         */
        sum = 0;
        for (i = 0; i < n; i++) {
            sum = sum + s[i];
        }
        if(weight == sum) {
            for (i = 0; i < n; i++) {
                printf("%d ", s[i]);
            }
            result = 1;
            printf("\n");
        }
        return;
    }
    for (i = pos; i < m; i++) {
        // swap solution
        tmp = s[i];
        s[i] = s[got];
        s[got] = tmp;
        combination(s, m , n, i + 1, got + 1);
        tmp = s[i];
        s[i] = s[got];
        s[got] = tmp;
    }
}
int main() {
    int m, n, i, tmp, sum = 0;
    scanf("%d", &m);
    int s[m];
    if(m > 0) {
        /* 
         * liststatus 用來記錄是否有不符合規定的砝碼重量
         * 若為0，表示所有的砝碼重量都符合規定
         * 若為1，表示其中有不符合規定的砝碼重量
         */
        int liststatus = 0;
        for(i = 0; i < m; i++) {
            scanf("%d", &tmp);
            //檢查砝碼重量是否大於零
            if(tmp > 0) {
                s[i] = tmp;
                sum = sum + tmp;
            } else {
                liststatus = 1;
                break;
            }
        }
        if(liststatus == 0) {
            scanf("%d", &n);
            weight = n;
            //檢查欲求的克數，是否超過所有砝碼的總重量
            if(n > sum) {
                printf("error\n");
            } else {
                /*
                 * 由於此次作業的規定是要拿m個砝碼湊出n克的重量
                 * 也就是說這是一個組合的問題，隨意從m個砝碼取出幾個，看總重量是否符合n克
                 * 首先得先列出Cm取1到Cm取m的所有組合，再從中判斷是否有符合要求的組合並印出
                 */
                for(i = 1; i <= m; i++) {
                    combination(s, m, i, 0, 0);
                }
            }
        } else {
            printf("error\n");
        }
        if(result == 0) {
            printf("-1\n");
        }
    }
    return 0;
}