算法设计与分析 5.2 洪尼玛的围栏

题目描述：

洪尼玛有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

样例输出：

No
Yes

思路：

回溯法的应用，有一说一，这节课我翘了去打球了，所以理解的不是很好，虽然用网上的代码修修改改做出来了，但是确实讲不出一个清晰的思路。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool generate(int i, vector<int >& nums, int target, int bucket[]) {
    if (i >= nums.size()) {
        return bucket[0] == target && bucket[1] == target && bucket[2] == target;
    }
    for (int j = 0; j < 3; j++) {
        if (bucket[j] + nums[i] > target) {
            continue;
        }
        bucket[j] += nums[i];
        if (generate(i + 1, nums, target, bucket)) {
            return true;
        }
        bucket[j] -= nums[i];
    }
    return false;

}


bool makesjx(vector<int>& nums) {
    if (nums.size() < 3) {
        return false;
    }
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
    }
    if (sum % 3) {
        return false;
    }
    sort(nums.rbegin(), nums.rend());
    int bucket[3] = { 0 };
    return generate(0, nums, sum / 3, bucket);

}





int main() {

    vector<int> nums;
    int m;
    scanf("%d", &m);
    int ans1[6];
    for (int i = 1; i <= m; i++) {

        nums.clear();
        int n, temp;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &temp);
            nums.push_back(temp);
        }
        int len=
        ans1[i] = makesjx(nums);


    }
    for (int i = 1; i <= m; i++) {
        if (ans1[i] == 0) cout << "No" << endl;
        if (ans1[i] == 1)cout << "Yes" << endl;

    }

}