#include <iostream>
#include <algorithm>
using namespace std;

class Sticks
{
protected:
	int* a;
	int n;
	int sum;
	bool* used;
	bool DFS(int stickCount, int len, int index, int aim);
public:
	Sticks(int n);
	~Sticks();
	void ReadData();
	int DFS();
};

Sticks::Sticks(int n)
{
	this->n = n;
	a = new int[n];
	used = new bool[n];
}

Sticks::~Sticks()
{
	delete[] a;
	delete[] used;
}

void Sticks::ReadData()
{
	sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
}
// stickCount：下标index（含）前已经搜索过的组合成完整的长度为aim的长棍子的数量
// len：本次搜索已经构成的长度
// index：要搜索下标index（不含）之后的短棍子
// aim：目标长度
bool Sticks::DFS(int stickCount, int len, int index, int aim)
{
	if (stickCount == sum / aim)
	{
		return true;
	}
	for (int i = index + 1; i < n; i++)
	{
		if (used[i])
		{
			continue;
		}
		if (len + a[i] == aim)
		{
			used[i] = true;
			if (DFS(stickCount + 1, 0, -1, aim))
			{
				return true; //这里的程序结构很巧妙
			}
			used[i] = false;
			return false;
		}
		else if (len + a[i] < aim)
		{
			used[i] = true;
			if (DFS(stickCount, len + a[i], i, aim))
			{
				return true;
			}
			used[i] = false;
			if (len == 0)
			{
				return false;
			}
			while (a[i] == a[i + 1]) // 剪枝技巧之一
			{
				i++;
			}
		}
	}
	return false;
}

int Sticks::DFS()
{
	sort(a, a + n);
	reverse(a, a + n);
	for (int aim = a[0]; aim <= sum; aim++)
	{
		if (sum % aim == 0)
		{
			memset(used, false, sizeof(bool) * n);
			if (DFS(0, 0, -1, aim))
			{
				return aim;
			}
		}
	}
	return 0;
}

int main()
{
	int n = 0;
	cin >> n;
	while (n > 0)
	{
		Sticks obj(n);
		obj.ReadData();
		cout << obj.DFS() << "\n";
		cin >> n;
	}
	return 0;
}

• Re:参考了网上的思路，总算A了，此题真是回溯的神题啊！ (7) wq_gao_0731 2017-11-04 17:14:52
• Re:参考了网上的思路，总算A了，此题真是回溯的神题啊！ (1977) 1700831 2018-01-21 11:01:34
• Re:参考了网上的思路，总算A了，此题真是回溯的神题啊！ (1977) 1700831 2018-01-21 11:01:51