站长素材音效网江苏网站建设制作

本来不想用递归做的，最后还是用了

题目如下：

洪尼玛有 n 块长度不同的木板，他想用这些木板拼成一个等边三角形的围栏，好将他的草泥马养在这个围栏里面。现在，给你这 n 块木板的长度，洪尼玛想知道他能否拼成这个围栏？要求：n 块木板都得用上。
输入格式:
第一行为一个正整数 T ，表示有 T 组测试数据。
对于每组测试数据，第一行为一个正整数 n ，表示木板个数；第二行包含 n 个正整数，表示每块木板的长度。
对于 60% 的数据，1≤T≤5，3≤n≤5，每块木板长度大于等于 1 小于等于 100。
对于 100% 的数据，1≤T≤5，3≤n≤10 ，每块木板长度大于等于 1 小于等于 100 。
输出格式:
对于每一组测试数据输出一行。
如果能拼成围栏输出 Yes ，否则输出 No 。
输入样例:
2
4
1 2 3 4
4
1 2 3 3

高中同学问的

最后是用了递归，受不了，本来以为找到了一个优解，最后是根本不行

还是用了递归

代码如下：

#include<stdio.h>
void sort(int num[], int n);
int dg(int num[], int idx, int sum);
int tmp, occ[10];int main(void)
{int T, n;int plank[10];scanf("%d", &T);//开始输入并处理for(int x = 0; x < T; x++){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &plank[i]);tmp += plank[i];}if(tmp % 3){printf("No");break;}tmp /= 3;//排序sort(plank, n);//判断行不行if(dg(plank, n - 1, plank[n - 1]) && dg(plank, n - 2, plank[n - 2])  && dg(plank, n - 3, plank[n - 3]))printf("Yes");elseprintf("No");}
}
void sort(int num[], int n)
{for(int i = 0; i < n - 1; i++)for(int j = i + 1; j < n; j++)if(num[i] > num[j])num[i] ^= num[j] ^= num[i] ^= num[j];return;
}
int dg(int num[], int idx, int sum)
{if(sum > tmp || occ[idx])  return 0;else if(sum == tmp)  {occ[idx] = 1; return 1;}occ[idx] = 1;for(int i = idx - 1; i >= 0; i--)if(dg(num, i, sum + num[i]))return 1;return 0;
}