Matchsticks to Square LeetCode solution in Java

1
class Solution {
2
  public boolean makesquare(int[] M) {
3
    Arrays.sort(M);
4
    int total = 0;
5
    for (int i = 0; i < M.length; i++) total += M[i];
6
    side = total / 4;
7
    if ((float) total / 4 > side || M[M.length - 1] > side) return false;
8
    return btrack(M.length - 1, side, 0, M);
9
  }
10

11
  private int side;
12

13
  private boolean btrack(int i, int space, int done, int[] M) {
14
    if (done == 3) return true;
15
    for (; i >= 0; i--) {
16
      int num = M[i];
17
      boolean res;
18
      if (num > space) continue;
19
      M[i] = side + 1;
20
      if (num == space) res = btrack(M.length - 2, side, done + 1, M);
21
      else res = btrack(i - 1, space - num, done, M);
22
      if (res) return true;
23
      M[i] = num;
24
      while (i > 0 && M[i - 1] == num) i--;
25
    }
26
    return false;
27
  }
28
}