A trickier DFS, with a little bit complex recursion param tweak, and what's more important is pruning strategies.. or your code will TLE.
class Solution {
bool go(vector<bool> &m, int edge, int eleft, int etgt, vector<int> &in, int taken)
{
if(edge > ) return false;
if(edge == && eleft == etgt && in.size() == taken)
{
return true;
}
int last = -;
for(int i = in.size()-; i >=; i --)
{
if(m[i]) continue;
if(in[i] > eleft) continue; // because it is sorted
if(in[i] == last) continue; // important: critical pruning.
if(in[i] <= eleft)
{
m[i] = true;
bool fit = in[i] == eleft;
if(go(m, edge + (fit?:), fit?etgt:(eleft-in[i]), etgt, in, taken + ))
{
return true;
}
m[i] = false;
last = in[i];
}
}
return false;
}
public:
bool makesquare(vector<int>& nums) {
if(nums.size() < ) return false;
int sum = accumulate(nums.begin(), nums.end(), );
if(!sum || (sum % )) return false;
sort(nums.begin(), nums.end());
if (nums.back() > (sum/)) return false;
vector<bool> m(nums.size(), false);
int tgt = sum / ;
return go(m, , tgt, tgt, nums, );
}
};