题目链接：https://leetcode-cn.com/problems/matchsticks-to-square/
题目描述：
题解：
class Solution {
public:
bool makesquare(vector<int>& matchsticks) {
vector<bool> used(matchsticks.size(), false);
int sum = 0;
for(auto &item : matchsticks)
{
sum += item;
}
if(sum % 4 != 0)
return false;
int target = sum / 4;
sort(matchsticks.begin(), matchsticks.end());
return trackingBack(matchsticks, 0, 0, target, 4, used);
}
bool trackingBack(vector<int>& matchsticks,int index, int pathSum, int target, int k, vector<bool>& used)
{
if(k == 0)
return true;
if(pathSum == target)
return trackingBack(matchsticks, 0, 0, target, k - 1, used);
for(int i = index; i < matchsticks.size() && matchsticks[i] + pathSum <= target; i++)
{
if(used[i] == true)
continue;
if(i > 0 && matchsticks[i] == matchsticks[i - 1] && used[i - 1] == false)
continue;
pathSum += matchsticks[i];
used[i] = true;
if(trackingBack(matchsticks, i + 1, pathSum, target, k, used))
return true;
pathSum -= matchsticks[i];
used[i] = false;
}
return false;
}
};