Leetcode 473 Solution

This article provides solution to leetcode question 473 (matchsticks-to-square)

https://leetcode.com/problems/matchsticks-to-square

Solution

class Solution { public: bool makesquare(vector<int>& nums, vector<int>& sums, int i, int target) { if (sums[0] == target && sums[1] == target && sums[2] == target) return true;
if (i == nums.size()) return false;
for (int j = 0; j < sums.size(); j++) { if (sums[j] + nums[i] <= target) { sums[j] += nums[i]; if (makesquare(nums, sums, i + 1, target)) return true; sums[j] -= nums[i]; } }
return false; }
bool makesquare(vector<int>& nums) { int s = accumulate(nums.begin(), nums.end(), 0);
if (s % 4 || s == 0) return false;
vector<int> sums(4); sort(nums.begin(), nums.end(), greater<int>());
sums[0] = nums[0];
return makesquare(nums, sums, 1, s / 4); } };