We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Matchsticks to Square

Difficulty: Medium

Problem Description

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.

Key Insights

  • The perimeter of the square must equal the total length of all matchsticks.
  • Each side of the square must be equal, so the total length must be divisible by 4.
  • Backtracking can be used to explore all combinations of matchstick placements to see if a square can be formed.
  • Using a depth-first search (DFS) approach can help efficiently explore the possible arrangements.

Space and Time Complexity

Time Complexity: O(4^(n/4)) where n is the number of matchsticks, as we may explore all combinations of sides. Space Complexity: O(n) for the recursion stack.

Solution

The problem can be solved using a backtracking algorithm. The approach involves:

  1. Calculating the total length of the matchsticks and checking if it's divisible by 4. If not, return false.
  2. Sorting the matchsticks in descending order to optimize the backtracking (place larger matchsticks first).
  3. Using a recursive function to try and build each side of the square by adding matchstick lengths until all matchsticks are used or until the side length reaches the required length.
  4. If all sides are built successfully, return true.

Code Solutions

def makesquare(matchsticks):
    total_length = sum(matchsticks)
    if total_length % 4 != 0:
        return False
    side_length = total_length // 4
    matchsticks.sort(reverse=True)
    sides = [0] * 4

    def backtrack(index):
        if index == len(matchsticks):
            return sides[0] == sides[1] == sides[2] == sides[3] == side_length
        for i in range(4):
            if sides[i] + matchsticks[index] <= side_length:
                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]
        return False

    return backtrack(0)
← Back to All Questions