poj1011.c

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX 50

int find_solution(int size, int consumed, int min, int max, int *len, int *num);
void start(int);

int distinct;
int sum;

int main(int argc, char *argv[])
{
    while (1) {
        int n;
        scanf("%d", &n);
        if (n)
            start(n);
        else
            break;
    }

    return 0;
}

void start(int n)
{
    int i, raw[MAX]; // common iter & raw data
    int len[50], num[50]; // rehash
    /*int *len, *num; // rehash*/
    sum = 0;
    distinct = 0;

    memset(raw, 0, sizeof(raw));
    memset(len, 0, sizeof(len));
    memset(num, 0, sizeof(num));

    // get data
    while(n--) {
        scanf("%d", &i);
        sum += i;
        if (!raw[i-1]++)
            ++distinct;
    }

    // rehash data
    /*len = malloc(sizeof(int) * distinct);*/
    /*num = malloc(sizeof(int) * distinct);*/
    for (i = 0, distinct = 0; i < MAX; ++i) {
        if (raw[i]) {
            len[distinct] = i+1;
            num[distinct] = raw[i];
            ++distinct;
        }
    }

    // main loop
    for (i = len[distinct-1]; i < sum; ++i) {
        if (sum%i != 0)
            continue;

        if (find_solution(i, 0, 0, distinct-1, len, num)) {
            printf("%d\n", i);
            break;
        } else {
            continue;
        }
    }

    if (i == sum)
        printf("%d\n", sum);
    /*free(len);*/
    /*free(num);*/
}

int find_solution(int size, int consumed,int min, int max, int *len, int *num)
{
    int i;
    int ret;
    if (consumed == size) {
        consumed = 0;
        max = distinct;
    }
    while(num[max] == 0 && min <= max)
        --max;
    while(num[min] == 0 && min <= max)
        ++min;
    if (min > max)
        return consumed == 0 ? 1 : 0;
    if (len[min] + consumed > size)
        return 0;
    i = max+1;

    while (i-- > min) {
        if (consumed + len[i] > size || num[i] == 0)
            continue;

        --num[i]; // eat!
        ret = find_solution(size, consumed + len[i], min, i, len, num);
        if (ret)
            return 1;
        ++num[i]; // puke!
        if (consumed ==0)
            break;
        if (len[i] == size - consumed)
            break;
    }
    return 0;
}