c++实现n个木棒，需要用上所有木棒，围成一个正方形

思路：

首先判断是否可以围成正方形，能围成正方形的条件是所有木棒长度之和必须为4的倍数。接着，在满足能围成正方形的情况下，我们可以使用回溯算法，枚举每一个木棒在正方形的哪个位置放置。具体步骤如下：

1. 计算所有木棒长度之和sum，判断是否为4的倍数，若不是则无法围成正方形，返回false。

2. 定义四个变量side，表示正方形的四条边的长度，初始化为0。

3. 对所有木棒进行全排列，枚举每一种排列方法。

4. 对于每一种排列方法，依次取出每个木棒，并枚举它可能的放置位置。若该木棒可以放在当前位置，则计算该位置更新后的边长，并递归进入下一层。

5. 若所有木棒均已放置完成，则检查四个边长是否相等且大于0，若成立则说明可以围成正方形，返回true。

6. 若在放置某个木棒时，发现该木棒无法放置，则回溯到上一层，换一个放置位置或尝试下一个木棒。

代码实现如下：

bool dfs(vector<int>& nums, int used, int side[4], int cur) {
    if (cur == 4) {  // 所有木棒均已放置完成
        for (int i = 0; i < 4; ++i) {
            if (side[i] != side[0] || side[i] == 0)  // 四个边长不相等或有边长为0，无法围成正方形
                return false;
        }
        return true;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (((used >> i) & 1) == 0) {  // 当前木棒未被使用
            for (int j = 0; j < 4; ++j) {  // 枚举放置位置
                if (side[j] + nums[i] > sum / 4)  // 放置后边长超过sum/4，则无法放置
                    continue;
                int old_side = side[j];
                side[j] += nums[i];
                if (dfs(nums, used | (1 << i), side, cur + (side[j] == sum / 4)))  // 当前木棒放置成功，进入下一层
                    return true;
                side[j] = old_side;  // 回溯
            }
        }
    }
    return false;
}

bool makesquare(vector<int>& nums) {
    int n = nums.size(), side[4] = {0};
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 4 != 0)  // 无法围成正方形
        return false;
    sort(nums.rbegin(), nums.rend());  // 从大到小排序，先尝试放置大的木棒，更容易满足条件
    return dfs(nums, 0, side, 0);
}

时间复杂度分析：

全排列的时间复杂度为O(n!)，而对于每种排列又需要枚举所有可能的放置位置，即总时间复杂度为O(4^n*n!)，其中n为木棒数。但是由于把大的木棒先放置可以更快地满足条件，因此实际运行时间会更快。