Solution: Matchsticks to Square

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #473 (Medium): Matchsticks to Square

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

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.
Visual:

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
• 0 <= matchsticks[i] <= 10^9

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

At first glance, this problem seems rather straightforward: find the total length of the matchsticks in M, figure out how long each side of the square must be, then find every combination of matchsticks that can add up to side. If four unique sets of matchsticks each add up to side, then we can return true.

The fact that the constraint upon the only imput is so low would seem to suggest that an O(2^N) solution is appropriate. There are, however, a few things we can do to optimize this process. The first key realization is that we can, in fact, use a greedy approach.

Consider the case of M = [1,1,1,2,2,2,3]. In this case, we can easily see that the total is 12 and thus side = 3. If we were to start iterating through M to find multiples of 3, we'd first group together the first three elements and then also find the last element, but be unable to make two more 3s from the middle elements of M. This would perhaps suggest that a greedy approach will not work, because it's readily apparent that we need to save the 1s to pair up with the 2s to make three of the four sides.

But that also suggests the solution, which is that we can use a greedy approach if we iterate through M in descending order. That way, each 2 will naturally seek out its matching 1 before we could ever attempt to match the 1s together in a less efficient manner.

That means that we can just use a recursive backtracking helper (btrack) to help find the side groups in M. But first, we can take care of some edge cases: If the total sum of M is not divisble by 4, or if any single matchstick in M is longer than the calculated side, then a solution is impossible and we should return false.

As for our recursive helper, it will need to iterate through the sorted M multiple times, attempting to build up groups that match side. We'll also keep track of how many groups we've found (done), and whenever we find a match, start btrack back at the beginning with done incremented.

(Note: When incrementing done and starting the recursive helper over, we can start at index 1 instead of index 0 because M[0] will always be a part of the first grouping.)

Once we've finished 3 groups, we can go ahead and return true, because we know that the remaining pieces must add up to side. If at any point we reach the end of M without finishing the current group, however, we should return false.

When attempting to add a piece to the current group, we can obviously skip pieces that are larger than the remaining space, as well as pieces that have already been used. Normally, this would require some kind of additional array or set to keep track of the used pieces, but we can use an in-place approach with M and just replace the used values with a value larger than side. This will simplify the check to skip elements to just one conditional.

(Note: If you don't want to modify the input, you could use a single integer and bit manipulation to achieve the same result in O(1) space. Sorting M will still take O(N) space if you don't want to modify M, however, and in any case, we'll be using O(N) space for the recursion stack.)

If an attempted piece turns out to be unsuccessfully and we're returned back up the recursion stack, we should remember to backtrack the current index (i) of M to its previous value (num).

• Time Complexity: O(2^N) where N is the length of M for the attempted combinations of elements in M
• Space Complexity: O(N) for the recursion stack

Implementation:

Java makes it more complicated to reverse sort a primitive array, so we can just use a simple sort and then iterate through M backwards instead.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var makesquare = function(M) {    let n = M.length, side = M.reduce((a,c) => a + c) / 4    M.sort((a,b) => b - a)    if (side !== ~~side || M[0] > side) return false    const btrack = (i, space, done) => {        if (done === 3) return true        if (i === n) return false        let num = M[i]        if (num > space)            return btrack(i+1, space, done)        M[i] = side + 1        if (num === space)            return btrack(1, side, done+1)        else {            if (btrack(i+1, space-num, done)) return true            M[i] = num            return btrack(i+1, space, done)        }    }    return btrack(0, side, 0)};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:    def makesquare(self, M: List[int]) -> bool:        n, side = len(M), sum(M) / 4        M.sort(reverse=True)        if side != floor(side) or M[0] > side:            return False        def btrack(i, space, done):             if done == 3: return True            if i == n: return False            num = M[i]            if num > space:                return btrack(i+1, space, done)            M[i] = side + 1            if num == space:                return btrack(1, side, done+1)            else:                if btrack(i+1, space-num, done): return True                M[i] = num                return btrack(i+1, space, done)        return btrack(0, side, 0)

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {    public boolean makesquare(int[] M) {        Arrays.sort(M);        int total = 0;        for (int i = 0; i < M.length; i++) total += M[i];        side = total / 4;        if ((float)total / 4 > side || M[M.length-1] > side) return false;        return btrack(M.length-1, side, 0, M);    }    private int side;    private boolean btrack(int i, int space, int done, int[] M) {        if (done == 3) return true;        if (i == -1) return false;        int num = M[i];        if (num > space)            return btrack(i-1, space, done, M);        M[i] = side + 1;        if (num == space)            return btrack(M.length-2, side, done+1, M);        else {            if (btrack(i-1, space-num, done, M)) return true;            M[i] = num;            return btrack(i-1, space, done, M);        }    }}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {public:    bool makesquare(vector<int>& M) {        sort(M.begin(), M.end(), greater<int>());        int total = accumulate(M.begin(), M.end(), 0);        side = total / 4;        if ((float)total / 4 > side || M[0] > side) return false;        return btrack(0, side, 0, M);    }private:    int side;    bool btrack(int i, int space, int done, vector<int>& M) {        if (done == 3) return true;        if (i == M.size()) return false;        int num = M[i];        if (num > space)            return btrack(i+1, space, done, M);        M[i] = side + 1;        if (num == space)            return btrack(1, side, done+1, M);        else {            if (btrack(i+1, space-num, done, M)) return true;            M[i] = num;            return btrack(i+1, space, done, M);        }    }};