LeetCode Solutions

Time: $O(2^n)$

Space: $O(2^n)$

			

class Solution {
 public:
  bool makesquare(vector<int>& matchsticks) {
    if (matchsticks.size() < 4)
      return false;

    const int perimeter = accumulate(begin(matchsticks), end(matchsticks), 0);
    if (perimeter % 4 != 0)
      return false;

    sort(begin(matchsticks), end(matchsticks), greater<int>());
    return dfs(matchsticks, 0, vector<int>(4, perimeter / 4));
  }

 private:
  bool dfs(const vector<int>& matchsticks, int selected, vector<int>&& edges) {
    if (selected == matchsticks.size())
      return all_of(begin(edges), end(edges),
                    [](int edge) { return edge == 0; });

    for (int i = 0; i < 4; ++i) {
      if (matchsticks[selected] > edges[i])
        continue;
      edges[i] -= matchsticks[selected];
      if (dfs(matchsticks, selected + 1, move(edges)))
        return true;
      edges[i] += matchsticks[selected];
    }

    return false;
  }
};

			

class Solution {
  public boolean makesquare(int[] matchsticks) {
    if (matchsticks.length < 4)
      return false;

    final int perimeter = Arrays.stream(matchsticks).sum();
    if (perimeter % 4 != 0)
      return false;

    int[] edges = new int[4];
    Arrays.fill(edges, perimeter / 4);
    Arrays.sort(edges); // can't do "Arrays.sort(edges, (a, b) -> b - a);" in Java
    return dfs(matchsticks, matchsticks.length - 1, edges);
  }

  private boolean dfs(int[] matchsticks, int selected, int[] edges) {
    if (selected == -1)
      return Arrays.stream(edges).allMatch(edge -> edge == 0);

    for (int i = 0; i < 4; ++i) {
      if (matchsticks[selected] > edges[i])
        continue;
      edges[i] -= matchsticks[selected];
      if (dfs(matchsticks, selected - 1, edges))
        return true;
      edges[i] += matchsticks[selected];
    }

    return false;
  }
}

			

class Solution:
  def makesquare(self, matchsticks: List[int]) -> bool:
    if len(matchsticks) < 4:
      return False

    perimeter = sum(matchsticks)
    if perimeter % 4 != 0:
      return False

    A = sorted(matchsticks)[::-1]

    def dfs(selected: int, edges: List[int]) -> bool:
      if selected == len(A):
        return all(edge == edges[0] for edge in edges)

      for i, edge in enumerate(edges):
        if A[selected] > edge:
          continue
        edges[i] -= A[selected]
        if dfs(selected + 1, edges):
          return True
        edges[i] += A[selected]

      return False

    return dfs(0, [perimeter // 4] * 4)