aboutsummaryrefslogtreecommitdiff
path: root/matchsticks_square.cpp
blob: f2422b83f332c2ff93daad3f7d2e77220e719e12 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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";
}