Skip to content

Instantly share code, notes, and snippets.

@s4553711
Created June 2, 2018 13:46
Show Gist options
  • Save s4553711/f5dc32fb1501e718a7f5b2b09fa6596d to your computer and use it in GitHub Desktop.
Save s4553711/f5dc32fb1501e718a7f5b2b09fa6596d to your computer and use it in GitHub Desktop.
class Solution {
public:
bool makesquare(vector<int>& nums) {
if (nums.empty() || nums.size() < 4) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 4 != 0) return false;
int n = nums.size(), all = (1 << n) - 1, target = sum/4;
vector<int> masks, validHalf(1<<n, false);
for(int i = 0; i < all; i++) {
int curSum = 0;
for(int j = 0; j <= 15; j++) {
if ((i >> j) & 1) curSum += nums[j];
}
if (curSum == target) {
for(int mask: masks) {
if ((mask & i) != 0) continue;
int half = mask | i;
validHalf[half] = true;
if (validHalf[all ^ half]) return true;
}
masks.push_back(i);
}
}
return false;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment