1011.cpp

非常好的C++学习源码,里面包括各种算法的实现,二叉的的前中后序遍历等

#include<iostream>
#include<memory.h>
using namespace std;
int a[65],b[65],total,l,n;

int compare(const void *ele1,const void *ele2)
{
	int *p1, *p2;
	p1=(int *)ele1;
	p2=(int *)ele2;
	return *p2-*p1;
}

bool f(int k,int left)
{
	int i;
	if ((k==0)&&(left==0))
		return (true);
	if (left==0)
		left=l;
	for (i=0;i<n;i++)
	{
		if ((b[i]==0)&&(a[i]<=left))
		{
			if (i>0)
			{
				if ((a[i-1]==a[i])&&(b[i-1]==0))
					continue;
			}
			b[i]=1;
			if (f(k-1,left-a[i]))
				return (true);
			else
			{
				b[i]=0;
				if ((left==l)||(a[i]==left))
					return false;
			}
		}
	}
	return false;
}

int main()
{
	int i,t;
	while(1)
	{
		t=0;
		cin>>n;
		if (n==0)
			break;
		total=0;
		for (i=0;i<n;i++)
		{
			cin>>a[i];
			total=total+a[i];
		}
		qsort (a,n,sizeof(int),compare);
		for (l=a[0];l<=(total/2+1);l++)
		{
			if ((total%l)!=0)
				continue;
			memset(b,0,sizeof(b));
			if (f(n,l))
			{
				cout<<l<<endl;
				t=1;
				break;
			}
		}
		if (t==0)
			cout<<total<<endl;
	}
	return 0;
}