火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。如果你能使这个正方形，则返回 true ，否则返回 false 。

回溯，根据先决条件判断出变长，轮询，不满足则剪枝，减少判断次数

class Solution 
{
public:bool makesquare(vector<int>& matchsticks) {if (matchsticks.size() < 4) {return false; // 边数小于4}int nSum = accumulate(matchsticks.begin(), matchsticks.end(), 0);if (nSum % 4) {return false; // 和不是4的倍数}// 从大到小排序，优先选用大的边可以令不成功的情况更快返回sort(matchsticks.begin(), matchsticks.end(), greater<int>()); vector<int> bucket(4); // 定义4个边的值return dfs(0, matchsticks, nSum / 4, bucket);}//index为当前遍历下标，matchsticks为边长，target为目标边长，bucket表示当前每条边的长度bool dfs(int nIndex, const vector<int>& matchsticks,const int& target, vector<int>& bucket) {if (nIndex >= matchsticks.size()) // 每条边都用了{return (bucket[0] == bucket[1]) && (bucket[0] == target);}for (int i = 0; i < 4; i++) { // 将当前的边放在4个桶中分别尝试if (bucket[i] + matchsticks[nIndex] > target){// 说明不可以放在这个边上continue; }// 否则放入该边后继续dfsbucket[i] += matchsticks[nIndex]; if(dfs(nIndex + 1, matchsticks, target, bucket)){return true;}//删除边长bucket[i] -= matchsticks[nIndex]; }return false;}
};