473. Matchsticks to Square LeetCode Solution

In this guide, you will get 473. Matchsticks to Square LeetCode Solution with the best time and space complexity. The solution to Matchsticks to Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Matchsticks to Square solution in C++
Matchsticks to Square solution in Java
Matchsticks to Square solution in Python
Additional Resources

473. Matchsticks to Square LeetCode Solution image

Problem Statement of Matchsticks to Square

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

473. Matchsticks to Square LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

473. Matchsticks to Square LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

473. Matchsticks to Square LeetCode Solution in Python

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)
 # code by PROGIEZ