Matchsticks to Square LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool makesquare(vector<int> &matchsticks) {
4
    int goal = 0, totalSum = 0;
5
    for (int i : matchsticks) {
6
      totalSum += i;
7
    }
8
    goal = totalSum / 4;
9
    sort(matchsticks.begin(), matchsticks.end(),
10
         [](auto left, auto right) { return left > right; });
11
    int b = 0;
12
    if (totalSum % 4) {
13
      return false;
14
    }
15
    return backtrack(0, b, 0, goal, 4, matchsticks);
16
  }
17

18
  bool backtrack(int start, int &b, int sum, int &goal, int groups, vector<int> &matchsticks) {
19
    if (sum == goal) {
20
      // set sum to 0, groups--
21
      return backtrack(0, b, 0, goal, groups - 1, matchsticks);
22
    }
23
    if (groups == 1) {
24
      return true;
25
    }
26
    for (int i = start; i < matchsticks.size(); i++) {
27
      if ((i > 0) && (!(b & (1 << (i - 1)))) && (matchsticks[i] == matchsticks[i - 1])) {
28
        continue;
29
      }
30
      // if element not used and element value doesnt go over group sum
31
      if (((b & (1 << i)) == 0) && (sum + matchsticks[i] <= goal)) {
32
        // set element to used, recursion
33
        b ^= (1 << i);
34
        if (backtrack(i + 1, b, sum + matchsticks[i], goal, groups, matchsticks)) {
35
          return true;
36
        }
37
        // if here, received a false, set element to unused again
38
        b ^= (1 << i);
39
      }
40
    }
41
    return false;
42
  }
43
};