# Funny Solution without DFS，Just random

• because only 15 matchstick

so，just random

• first, we look it's can split two array: a & b
• second, look a & b can split two array

easy and funny : ) the time just guess. obviously it's be sure

class Solution {
public:
bool makesquare(vector<int>& nums) {
int total = 0;
for_each(nums.begin(), nums.end(), [&](const int num){
total += num;
});
int target = total/4;
if(target * 4 != total || total == 0) return false;

srand((int)time(NULL));
vector<int> a;
vector<int> b;
int time = 500;
while(time--){
if(!canBin(nums, a, b, target * 2)) continue;
vector<int> aa,bb;
if(canBin(a, aa, bb, target) && canBin(b, aa, bb, target)) return true;
}

return false;
}

bool canBin(vector<int>&nums,vector<int>& a, vector<int>& b, int target){
a.clear();
b.clear();

int suma = 0,sumb = 0;
for(int i=0;i<nums.size();i++){
if(i%2) a.push_back(nums[i]),suma+=nums[i];
else b.push_back(nums[i]),sumb+=nums[i];
}

if(suma == sumb) return true;
int tmp = 0;
int time = 10;
while(time--){
if(suma == sumb) break;

if(rand()%2 && a.size()>0 && b.size()>0){ // change item value, make suma equal sumb
int aidx = rand()%a.size();
int bidx = rand()%b.size();

suma = suma - a[aidx] + b[bidx];
sumb = sumb - b[bidx] + a[aidx];
tmp = a[aidx];
a[aidx] = b[bidx];
b[bidx] = tmp;
} else{  // add & remove item value . make suma equal sumb
if(suma > sumb){
tmp = a.back();
b.push_back(a.back());
a.pop_back();
sumb += tmp;
suma -= tmp;
} else{
tmp = b.back();
a.push_back(b.back());
b.pop_back();
suma += tmp;
sumb -= tmp;
}
}

}

return suma == sumb;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.