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

#include<vector>
#include<list>
#include<iostream>

using namespace std;

typedef vector<int> intArray_t;

int sumOfArray(const vector<int> &array) {
	int sum = 0;
	int size = array.size();
	for (int i = 0; i < size; i++) {
		sum += array.at(i);
	}
	return sum;
}

bool maxDivFun(list<int> &array, vector<intArray_t> &result, int groupSize, int preSize, vector<int> &preArray, list<int>::iterator iter) {
	while (iter != array.end()) {
		if ((preSize + *iter) <= groupSize) {
			preArray.push_back(*iter);
			bool isFirst = false;
			if (iter == array.begin()) {
				isFirst = true;
			}
			array.erase(iter++);
			if ((preSize + preArray.back()) == groupSize) {
				if (array.empty()) {
					result.push_back(preArray);
					return true;
				}
				else {

					
					list<int> retList(array.begin(), array.end());
					vector<int> grpArray(1, retList.back());
					retList.pop_back();
					if (maxDivFun(retList, result, groupSize, grpArray.at(0), grpArray, retList.begin())) {
						result.push_back(preArray);
						return true;
					}
					
					if (!isFirst)
						iter--;
				}
			}
			else if (isFirst) {
				if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter))
					return true;
			}
			else if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter--))
				return true;
			if (isFirst) {
				iter = array.begin();
				array.insert(iter, preArray.back());
			}
			else
				array.insert(++iter, preArray.back());
			preArray.pop_back();
		}
		else
			break;
	}
	return false;
}

void maxDiv(const vector<int> &array, vector<intArray_t> &result) {
	if (array.empty())
		return;
	list<int> retList(array.begin(), array.end());
	retList.sort();
	int maxNum = retList.back();
	vector<int> preArray(1, maxNum);
	if (retList.size() == 1) {
		result.push_back(preArray);
		return;
	}
	retList.pop_back();
	int sum = sumOfArray(array);
	if (sum % maxNum == 0) {
		result.push_back(preArray);
		int n = 0;
		while (retList.back() == maxNum) {
			result.push_back(preArray);
			retList.pop_back();
			if (retList.empty())
				return;
			n++;
		}
		preArray.at(0) = retList.back();
		retList.pop_back();
		if (maxDivFun(retList, result, maxNum, preArray.at(0), preArray, retList.begin())) {
			return;
		}
		retList.push_back(preArray.at(0));
		for (; n != 0; n--) {
			retList.push_back(maxNum);
		}
		preArray.at(0) = maxNum;
		result.clear();
	}
	for (int i = maxNum + 1; i <= sum; i++) {
		if (sum % i == 0 && maxDivFun(retList, result, i, preArray.at(0), preArray, retList.begin())) {
			break;
		}
	}
}

int main() {
	int a[10000];
	//int a[] = { 1, 2, 4, 5, 100 };
	//int a[] = { 1, 1, 1, 1, 1, 1 };
	//int a[] = { 3, 3, 4, 6, 2 };
	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++) {
		a[i] = i + 1;
	//	while ((a[i] = (rand() % 1000)) == 0);
	}
	vector<int> array(a, a + (sizeof(a)/sizeof(int)));
	vector<intArray_t> result;
	maxDiv(array, result);
	cout << "{";
	int resultSize = result.size();
	for (int i = 0; i < resultSize; i++) {
		if (i != 0)
			cout << ", ";
		cout << "{";
		vector<int> group = result.at(i);
		int groupSize = group.size();
		for (int j = 0; j < groupSize; j++) {
			if (j != 0)
				cout << ", ";
			cout << group.at(j);
		}
		cout << "}";
	}
	cout << "}";
	cout << "\n";
	cout << "The max group num that can divide to have same sum group is: " << resultSize;
	return 0;
}