Skip to content

473. Matchsticks to Square 👍

  • Time: $O(2^n)$
  • Space: $O(2^n)$
 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
class Solution {
 public:
  bool makesquare(vector<int>& matchsticks) {
    if (matchsticks.size() < 4)
      return false;

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

    ranges::sort(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 ranges::all_of(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, std::move(edges)))
        return true;
      edges[i] += matchsticks[selected];
    }

    return false;
  }
};

 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
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) -> Integer.compare(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;
  }
}

 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
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)