POJ.1011adv

sticks

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

int sort(int *array,int num);
int find_candidates(int *candi_len,int max_stick,int sum);
int dfs(int len,int num_sticks,int candi_len);
int *ifused = NULL;
int num = 0;
int sum = 0;
int *sticks = NULL;
int sum_zero = 0;

int main()
{
	int i;
	int candi_num;
	int *candi_len = NULL;
	int *left = NULL;
	scanf("%d",&num);

	while ( num != 0) {
        	int i;
		sticks=(int*)malloc(sizeof(int)*num);
        	for (i = 0; i < num; i++) {
            		scanf("%d", &sticks[i]);
        	}
		sum = sort(sticks,num);
		sum_zero = sum;
		candi_len = (int *)malloc(sizeof(int)*num);
		ifused = (int *)malloc(sizeof(int)*num);
		memset(ifused,0,sizeof(int)*num);
		candi_num = find_candidates(candi_len,sticks[0],sum);
		
		for(i=0;i<candi_num;i++){
			if(dfs(candi_len[i],sum/candi_len[i],candi_len[i]))
				break;
			else
			{
				memset(ifused,0,sizeof(int)*num);
				sum_zero = sum;
			}
		}
		printf("%d\n",candi_len[i]);
		scanf("%d", &num);
	}
	return 0;
	
}

int sort(int *array,int num){
	int max=0;
	int index;
	int sum=0;
	for(int i=0;i<num;i++)
	{
		max = array[i];
		index = i;
		for(int j=i;j<num;j++)
		{
			if (array[j]>max)
			{
				max = array[j];
				index = j;
			}
		}
		array[index]=array[i];
		array[i]=max;
		sum+=array[i];
	}
	return sum;
}


int find_candidates(int *candi_len,int max_stick,int sum){
	int num_candi=0;
	int i;
	int j=0;
	for(i=max_stick;i<=sum;i++)
	{
		if(sum%i==0)
		{
			candi_len[j++]=i;
			num_candi++;
		}
		
	}
	
	return num_candi;
	
}

int dfs(int len,int num_sticks,int candi_len)
{
	int i,j;
	int stick_len;
	int record;
	if(len==candi_len&&num_sticks==1)
		return 1;
	for(i=0;i<num;i++)
	{
		if(sum_zero<len)
			return 0;
		if(sum_zero==len)
			return 1;

		stick_len = sticks[i];
		if(ifused[i]==0&&stick_len<=len)
		{
			int next_length;
			ifused[i]=1;
			sum_zero-=stick_len;

			next_length = len-stick_len;
			if(next_length == 0)
			{
				next_length = candi_len;
				num_sticks -= 1;
			}

			record = dfs(next_length,num_sticks,candi_len);
			
			if(record==0)
			{
				ifused[i]=-1;

				if(len==candi_len){	
					ifused[i]=0;
					sum_zero += sticks[i];
					return 0;
				}

				for(j=i+1;j<num;j++)
				{
					if(sticks[j]==stick_len&&ifused[j]==0)
					{
						ifused[j]=-1;
						sum_zero -= sticks[i];
					}
				}
			}
			else
			{	
				for(j=i;j>=0;j--)
				{
					if(ifused[j]==-1)
					{
						ifused[j]=0;
						sum_zero += sticks[j];
					}
				}
				break;
			}
		}
	}
	if(i==num)
	{
		for(j=0;j<num;j++)
		{
			if(ifused[j]==-1)
			{
				ifused[j]=0;
				sum_zero += sticks[j];
			}
		}
		return 0;
	}
	else
	{
		/*
		while(ifused[i]==-1&&i>=0)
		{
			ifused[i--]=0;
		}
		*/
		
		return 1;
	}
}