POJ.1011

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 *sticks = NULL;

int main()
{
	int i,sum;
	int candi_num;
	int result;
	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);
		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);
			}
		}
		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;
	int stick_len;
	int record;
	if(len==0&&num_sticks==1)
		return 1;
	else if(len==0)
	{
		return dfs(candi_len,num_sticks-1,candi_len);
	}
	for(i=0;i<num;i++)
	{
		stick_len = sticks[i];
		if(ifused[i]==0&&stick_len<=len)
		{
			ifused[i]=1;
			record = dfs(len-stick_len,num_sticks,candi_len);
			if(record==0)
			{
				ifused[i]=0;
				if(len==candi_len){			
					return 0;
				}
			}
			else
			{
				break;
			}
		}
	}
	if(i==num)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}