回溯算法，基本上就是：
追一個MM，但也許你還是情竇初開的新手，不知道如何才能討得MM的歡心，于
是你只好一條路一條路的試，MM不開心了，你就回溯回去換另一種方式。當然
其間你也許會從某些途徑得到一些經驗，能夠判斷哪些路徑不好，會剪枝（這
就是分支估界了）。你也可以隨機選擇一些路徑來實施，說不定能立桿見影（
這就是回溯的優化了）但總的來說，你都需要一場持久戰。。。。
該算法一般也能得到最優解，因為大多數MM會感動滴！！但其缺點是開銷大！
除非你是非要談一場戀愛不可，否則不推薦使用。特別是你可能還有許多其他
的事情要做，比如學習，比如事業。。。。

下面是pku1011絕對經典的DFS+剪枝的利用了回溯的思想好題的算法。
值得大家去學習和研究下，怎樣剪枝效果最好。


#include <iostream>
//#include <fstream>
using namespace std;
int flag = 0;
int lay = 0;
int l[100];
int a[100];
int Qsort( int t[], int start, int end )
{
	int i;
	t[0] = t[start];
	i = 0; // i==0表示t[up]跟t[0]比較， i==1表示t[down]跟t[0]比較。
	int up = end;
	int down = start;
	while ( up != down )
	{
		if ( i == 0 && t[up] <= t[0] )
		{
			up--;
			continue;
		}
		if ( i == 0 && t[up] > t[0] )
		{
			t[down] = t[up];
			i = 1;
			down++;
			continue;
		}
		if ( i == 1 && t[down] >= t[0] )
		{
			down++;
			continue;
		}
		if ( i == 1 && t[down] < t[0] )
		{
			t[up] = t[down];
			i = 0;
			up--;
		}
	}
	t[down] = t[0];
	return down;
}
void qs ( int t[], int start, int end )		//遞歸實現快排
{
	int mid;
	if ( start < end )
	{
		mid = Qsort(t,start,end);
		qs ( t,start,mid-1);
		qs ( t,mid+1,end);
	}
}
int f ( int t, int sum, int position, int max, int n )
{
	if ( t == sum )
	{
		if ( max-sum == sum )
		{
			flag = 1;
			return 1;
		}
		position = 1;
		while ( l[position] == 1 && position <= n )
			position++;
		if ( position > n )
			return 0;
		l[position] = 1;
		f ( a[position], sum , position+1, max-sum,n);
		l[position] = 0;
	if ( max-sum == sum )
		flag = 1;
	//	if ( flag == 1 )
	//		return 1;

	}
	else
	{
		int pos = position;
		while ( a[pos] + t > sum || l[pos] == 1 )
		{
			pos++;
			if ( pos > n )
				break;
		}
		if ( pos > n )
			return 0;
		position = pos;
		t+=a[position];
			if (a[position] != a[position-1])
			{
				l[position] = 1;
				f(t,sum,position+1,max,n);
				l[position] = 0;
			}
			else if (l[position-1] == 1)
			{
				l[position] = 1;
				f(t,sum,position+1,max,n);
				l[position] = 0;
			}
		if ( flag == 1 )
			return 1;
		
		if ( t != sum )
		{
			l[position] = 0;
			t -= a[position];
			f(t,sum,position+1,max,n);
		}
	}
	
	return 1;
}
int main ()
{
//	ofstream fop ("out.txt");
	int n,i;
	int sum;
	while ( scanf("%d",&n) && n!=0 )
	{
		for ( i = 1; i <= n; i++ )
			l[i] = 0;
		sum = 0;
		for ( i = 1; i <= n; i++ )
		{
			scanf("%d",&a[i]);
			if ( a[i] > 50 )
			{
				i--;
				n--;
				continue;
			}
			sum += a[i];
		}
		if ( n == 1 )
		{
	//		fop<<a[1]<<endl;
	//		flush(cout);
			cout<<a[1]<<endl;
			continue;
		}
		qs(a,1,n);
		a[0] = -1;
		for ( i = 1; i < 100; i++ )
			l[i] = 0;
		l[0] = 1;
		for ( i = a[1]; i<=(sum+1)/2; i++ )
		{
			if ( sum%i==0)
			{
				f(0,i,1,sum,n);
				if ( flag == 1 )
					break;
			}
		}
		if ( flag == 1 )
	//		fop<<i<<endl;
			cout<<i<<endl;
		else
//			fop<<sum<<endl;
			cout<<sum<<endl;
//		flush(cout);
		flag = 0;
		
	}
	return 1;
}