POJ 1011

#include<iostream>
#include<algorithm>
#define MAXN 65
using namespace std;

int _m[MAXN];
int _sum[MAXN];
bool mark[MAXN];
bool op(int a,int b);
bool boo;
int num;
int sum_all;
void search(int len,int index,int sum,int n,int time);
int main()
{
    //freopen("acm.acm","r",stdin);
    int    n;
    int i;
    int j;
    int sum;
    int max;
    int time;
    while(1)
    {
        scanf("%d",&n);
        if(!n)
            break;
        sum_all = 0;
        memset(mark,false,sizeof(mark));
        memset(_m,0,sizeof(_m));
        sum = 0;
        for(i = 0; i < n; ++ i)
        {
            scanf("%d",&_m[i]);
            sum += _m[i];
        }
        sort(_m,_m+n,op);
        for(i = 0; i < n; ++ i)
        {
            _sum[i] = _m[i];
        }
        max = *max_element(_m,_m+n);
        for(i = n-2; i >= 0; -- i)
        {
            _sum[i] += _sum[i+1];
        }

        for(i = max; i < sum; ++ i)
        {
            memset(mark,false,sizeof(mark));
            if(i > sum/2+1)
                continue;
            boo = false;
            if(sum % i != 0)
                continue;
            num = sum/i;
            time = 1;
            j = 0;
            while(_m[j] == i)
            {
                mark[j] = true;
                ++ j;
            }

            if(j == sum/i)
            {
                printf("%d ",i);
                break;
            }
            mark[j] = true;
            search(i,j,_m[j],n,time+j);
            mark[j] = false;
            if(boo)
            {
                printf("%d ",i);
                break;
            }
        }
        if(i == sum)
            cout<<sum<<endl;
    }
}

void search(int len,int index,int sum,int n,int time)
{
    if(time == num)
    {
        boo = true;
    }
    if(boo)
        return;
    int i;
    for(i = index+1; i < n; ++ i)
    {
        if(!mark[i])
        {
            if(!mark[i-1] && _m[i] == _m[i-1])
                continue;
            if(sum + _sum[i] < len)
            {
                break;
            }
            if(sum + _m[i] < len)
            {
                mark[i] = true;
                search(len,i,sum+_m[i],n,time);
                mark[i] = false;
                if(boo)
                    return;
            }
            else if(sum + _m[i] == len)
            {
                mark[i] = true;
                int k;
                for(k = 0; k < n; ++ k)
                {
                    if(!mark[k])
                        break;
                }
                mark[k] = true;
                search(len,k,_m[k],n,time+1);
                if(boo)
                    return;
                mark[i] = false;
                mark[k] = false;
                break;
            }
        }
    }
}

bool op(int a,int b)
{
    return a > b ;
}

关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。 

技术网站地址： vmfor.com