拼接木棍

转载 https://blog.csdn.net/weixin_45485187/article/details/103490709

这位老哥的解析写得很好了，书上错了两个地方都被他找到了 感谢！

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

int n;
int a[61];
int f;
int sum = 0;
int used[61];
int len;
int m;
int max_;

bool cmp(int a, int b)
{
	return a > b;
}

void Read()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		sum +=a[i] ;
	}
	sort(a + 1,a + n + 1,cmp);
	max_ = a[1];
}

void DF(int k,int last,int rest)
//当前在接第k根，在接的这根的上一节木棍的下标last，这跟还剩rest到达len
{
	if (k == m)
	{
		f = 1;
		return;
	}
	int i, j;
	if (rest == 0)
	{
		for (i = 1; i <= n; i++)
			if (!used[i])
			{
				used[i] = 1;
				break;
			}
		DF(k + 1, i, len-a[i]);
		used[i] = 0;//若没有回溯 会导致错误
	}

	for (i = last+1; i <= n; i++)
	{
		if (!used[i] && rest >= a[i])
		{
			used[i] = 1;
			DF(k, i, rest - a[i]);
			used[i] = 0;
			if (f == 1)
				return;//若没有成功后马上回到停止 会导致超时
			j = i;
			while (i < n && a[i] == a[j])
				i++;
			if (i == n)
				return;
		}
	}

}


void Solve()
{
	for (len= max_; len <= sum; len++)
	{
		if (sum % len == 0)
		{
			m = sum / len;
			f = 0;
			memset(used, 0, sizeof(used));
			used[1] = 1;
			DF(1, 1, len-a[1]);
			if (f == 1)
			{
				printf("%d", len);
				break;
			}
		}

	}
	
}


int main()
{
	Read();
	Solve();
	return 0;
}