Matchsticks to Square

Patrick Leaton
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.

 

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] <= 10^8

 

The description was taken from https://leetcode.com/problems/matchsticks-to-square/.

Problem Solution

#O(2^N) Time, O(N) Space
class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        if sum(matchsticks)%4 != 0:
            return False
       
        target = sum(matchsticks)//4
        matchsticks.sort()
        if matchsticks[-1] > target:
            return False
       
        def backtrack(buckets:list) -> bool:
            if not matchsticks:
                return True
            candidate = matchsticks.pop()
            for i, bucket in enumerate(buckets):
                if bucket + candidate <= target:
                    buckets[i] += candidate
                    if backtrack(buckets):
                        return True
                    buckets[i] -= candidate
                if bucket == 0:
                    break
            matchsticks.append(candidate)
            return False
       
        return backtrack([0] * 4)

Problem Explanation


To solve this question, we would need to find out if we can rearrange these matchsticks into four equal sum partitions where no matchstick is split between multiple partitions.

This approach is a popular backtracking problem called Partition to K Equal Sum Subsets.

What we can do is initialize an array of four indices that we can picture as buckets.

Within each DFS path, we will pop a matchstick off of the input array and place it into one of the buckets that have a sum less than or equal to the target value.  Then, we will continue down the DFS path keeping the current combination array.  If we have gotten to a point where we have placed each matchstick, we know we have and can partition the matchsticks accordingly.  If not, we'll backtrack our placement choices and cycle the matchsticks back in to try again using different placement combinations.


First off, if the sum of the matchsticks isn't divisible by four then it wouldn't be possible to place these matchsticks into four equal sides.  

If this is the case, we will return false.

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

 

If that isn't the case, we will divide the input array sum by four.

This will give us the target value that each bucket needs to sum to.

        target = sum(matchsticks)//4

 

Now, let's go ahead and sort the array so we can check if the last matchstick within it is greater than the target value.  If it is, we couldn't possibly place that matchstick into a bucket and have it sum to the target value.  

If that's the case, we will return false.

        matchsticks.sort()
        if matchsticks[-1] > target:
            return False


Next, let's build our recursive, backtrack function.

This function will require a buckets variable.  This will basically be a combination array of size four that contains the sums for each subset within the current DFS path.

        def backtrack(buckets:list) -> bool:

 

Let's draw out what we are hoping to achieve with this function.

If we are given the input where matchsticks = [4,3,2,3,5,2,1], the total sum of matchsticks would be twenty.

In this case, we would have four subsets that each sum to five.  We would end up with the buckets [5, 5, 5, 5], four values that signify four partitioned subsets of which the sums are equal.

We would know that we achieved this by whether or not we used up all of the matchsticks from our input array.  That is our base case.

            if not matchsticks:
                return True

 

If we haven't, we will pop a matchstick off the end of the input array and place that matchstick into a bucket (an index), if that matchstick plus the value of the current bucket is less than equal to the target sum value. 

            candidate = matchsticks.pop()
            for i, bucket in enumerate(buckets):
                if bucket + candidate <= target:
                    buckets[i] += candidate

 

Now we have chosen to put a matchstick into one of the buckets, but we don't know if we made the right choice by placing it into whichever bucket it is now in.  To see, we will continue our DFS by using the current buckets combination and test whether we can place the remaining matchsticks into the remaining buckets with values less than the target.

We will know if this was the right choice if we hit our base case.

                    if backtrack(buckets):
                        return True

 

If not, we will backtrack the choice of placing the candidate matchstick into the current bucket and try to place it in a different bucket later on.

                    buckets[i] -= candidate

 

To avoid endless loops, we will need to see if after removing the current candidate from the current bucket, the bucket is now zero.

If it is, that means we were unsuccessful in our placings of this bucket and don't want to keep trying to place the same combination of matchsticks.  If we put a matchstick in and it didn't work, we don't want to put that same matchstick in and get the same result, so we will break from this bucket.

                if bucket == 0:
                    break

 

If we have iterated through each bucket and couldn't place the current candidate matchstick into any bucket that would result in our success, we will put it back into the array and return from this DFS path since it was not successful.

            matchsticks.append(candidate)
            return False


Now that our backtracking function is built, all we need to do is pass the initial four empty buckets that we are trying to partition.

        return backtrack([0] * 4)