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