aboutsummaryrefslogtreecommitdiff
path: root/matchsticks_square.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'matchsticks_square.cpp')
-rw-r--r--matchsticks_square.cpp46
1 files changed, 0 insertions, 46 deletions
diff --git a/matchsticks_square.cpp b/matchsticks_square.cpp
deleted file mode 100644
index f2422b8..0000000
--- a/matchsticks_square.cpp
+++ /dev/null
@@ -1,46 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- bool makesquare(vector<int> &matchsticks) {
- sort(matchsticks.begin(), matchsticks.end(), greater<int>());
- int total = accumulate(matchsticks.begin(), matchsticks.end(), 0);
- side = total;
- if ((float)total / 4 > side || matchsticks[0] > side)
- return false;
- return helper(0, side, 0, matchsticks);
- }
-
-private:
- int side;
- bool helper(int i, int space, int done, vector<int> &matchsticks) {
- if (done == 3)
- return true;
- for (; i < matchsticks.size(); i++) {
- int num = matchsticks[i];
- bool ans;
- if (num > space)
- continue;
- matchsticks[i] = side + 1;
- if (num == space)
- ans = helper(1, side, done + 1, matchsticks);
- else
- ans = helper(i + 1, space - num, done, matchsticks);
- if (ans)
- return true;
- matchsticks[i] = num;
- while (i < matchsticks.size() && matchsticks[i + 1] == num)
- i++;
- }
- return false;
- }
-};
-
-int main() {
- Solution obj;
- vector<int> matchsticks = {1, 1, 2, 2, 2};
- if (obj.makesquare(matchsticks))
- cout << "true";
- else
- cout << "false";
-}