Matchsticks To Square - Leetcode Solution

Problem Statement:

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.

Solution:

This problem can be solved using a recursive backtracking approach. We can start by checking if the sum of all matchsticks is divisible by 4 since that is a necessary condition for forming a square. Next, we can sort the matchsticks in non-increasing order since we want to use the longer matchsticks first. Then, we can start with four sides of the square and try to add the matchsticks to each side in a recursive manner.

The recursive function will take in four parameters: the current side we are adding matchsticks to, the index of the matchstick we are currently trying to add, an array of the current length of each side, and the target length of each side (which is the total sum of matchsticks divided by 4).

If we have added all the matchsticks to the four sides and they all have the same length, we can return true since we have formed a square. Otherwise, we can iterate through all the matchsticks and try adding them to the current side. If adding the matchstick to the current side does not cause it to exceed the target length, we can recursively call the function with the next matchstick and the updated side lengths. If all the recursive calls return false, we can remove the matchstick from the current side and try the next one.

At any point during the recursion, if we find that a side has a length greater than the target length, we can return false since we cannot form a square with these matchsticks.

Pseudocode:

function makesquare(matchsticks):
    totalSum = sum(matchsticks)
    if totalSum % 4 != 0:
        return false
    targetSide = totalSum / 4
    matchsticks.sort(reverse=True)
    return backtrack(0, 0, [0, 0, 0, 0], targetSide, matchsticks)

function backtrack(side, index, sideLengths, targetSide, matchsticks):
    # Base case: all matchsticks added and all sides have same length
    if index == len(matchsticks) and sideLengths[0] == sideLengths[1] == sideLengths[2] == sideLengths[3]:
        return true
    # Base case: side length exceeds target length
    if sideLengths[side] > targetSide:
        return false
    for i in range(index, len(matchsticks)):
        if matchsticks[i] == 0:
            continue
        matchstickLength = matchsticks[i]
        matchsticks[i] = 0
        newSideLengths = sideLengths.copy()
        newSideLengths[side] += matchstickLength
        if backtrack(side, i+1, newSideLengths, targetSide, matchsticks):
            return true
        matchsticks[i] = matchstickLength
    return false

Time Complexity: O(4^N) where N is the number of matchsticks.

Space Complexity: O(N) for the recursive call stack.

1