一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值

一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3

#include <iostream>
using namespace std;


int testShare(int *a,int n,int m,int sum,int groupSum,int *aux,int goal,int groupId)
{
	if(goal < 0)
		return 0;

	if(goal == 0)
	{
		groupId++;
		goal = groupSum;

		if(groupId == m+1)
			return 1;
	}

	for(int i = 0;i<n;i++)
	{
		if(aux[i] != 0)
			continue;

		aux[i] = groupId;
		if(testShare(a,n,m,sum,groupSum,aux,goal-a[i],groupId))
			return 1;

		//如果不适合恢复
		aux[i] = 0;
	}
	return 0;
}

int maxShare(int *a,int n)
{
	int sum = 0;
	
	int *aux = new int[n];

	for(int i = 0;i<n;i++)
		sum+=a[i];

	for(int m = n;m>=2;m--)
	{
		if(sum%m!=0)
			continue;

		for(int i = 0;i < n;i++)
		{
			aux[i] = 0;
		}

		if(testShare(a,n,m,sum,sum/m,aux,sum/m,1))
		{
			//打印分组情况
			cout << endl<<"分组情况"<<endl;
			for(int i = 0;i< n;i++)
				cout << aux[i]<<" ";
			delete[] aux;
			aux = NULL;
			return m;
		}
	}
	
}

int main()
{
	int a[] = {3,2,4,3,6};

	//打印数组值
	printf("数组的值：");
	for (int i = 0; i < 5; i++)
		printf(" %d ", a[i]);

	printf("\n可以分配的最大组数为：%d\n", maxShare(a, 5));

	system("pause");
	return 0;
}