unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 473: Matchsticks to Square

link

Adding up the matchsticks gives the square’s perimeter and the square’s expected side length is \frac{perimeter}{4}. Now, using all the matchsticks exactly once, we need to build the four sides–each side must have the expected length.

Backtracking

From a side’s point of view

We try making one side at a time using all combinations of unused sticks that has a total side length == expected_side_len. If longest stick is longer than the expected_side_len, we cannot make a square. We start with matchsticks sorted by length so as soon as a combination-sum is too big, latter sticks would not help that combination, so we can backtrack and try other combinations.

Say shortest stick’s length is m and expected side length is s, then the max recursion depth is d = 4 \cdot \frac{s}{m}. If there are n matchsticks, the cost of levels are like: n, (n-1), \ldots, (n-d+1). In other words, time complexity: \mathcal{O}(d! \cdot {n \choose d}), space complexity: \mathcal{O}(d).

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        def try_make_square(nsides: int, side_len: int, curr_len: int, used: Set[int]) -> bool:
            if nsides == 4:
                return True
            
            for i, stick_len in enumerate(matchsticks):
                if i in used:
                    continue
                new_len = curr_len + stick_len
                if new_len > side_len:
                    continue
                
                used.add(i)
                if new_len == side_len:
                    if try_make_square(nsides+1, side_len, 0, used):
                        return True
                else:
                    if try_make_square(nsides, side_len, new_len, used):
                        return True
                used.remove(i)
            
            return False

        perimeter = sum(matchsticks)
        side_len, r = divmod(perimeter, 4)
        if r != 0:
            return False
        if max(matchsticks) > side_len:
            return False

        return try_make_square(0, side_len, 0, set())

From a matchstick’s point of view

From a stick’s point of view, it must be assigned to one of the four sides. So, we can scan matchsticks left to right and try assigning current stick to each of the four sides. When all sticks have been assigned and each side has a total length == expected_side_len, we have been able to make the square.

Given there are n matchsticks, the recursion depth is now n and the width of a level is at most 4. Time complexity: \mathcal{O}(4^n), space complexity: \mathcal{O}(n).

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        def try_assign_to_side(
            stick_index: int, sides: List[List[int]], expected_side_len: int
        ) -> bool:
            if stick_index >= len(matchsticks):
                return all(sum(sticks) == expected_side_len for sticks in sides)
 
            current_stick_len = matchsticks[stick_index]
            for j in range(4):
                new_side_len = sum(sides[j]) + current_stick_len
                if new_side_len > expected_side_len:
                    continue
                sides[j].append(current_stick_len)
                if try_assign_to_side(stick_index + 1, sides, expected_side_len):
                    return True
                sides[j].pop()
            return False
 
        perimeter = sum(matchsticks)
        expected_side_len, r = divmod(perimeter, 4)
        if r != 0:
            return False
        if max(matchsticks) > expected_side_len:
            return False
 
        sides = [[] for _ in range(4)]
        return try_assign_to_side(0, sides, expected_side_len)

Like packing a bag, once big items have been placed, tiny items can be inserted in leftover nooks and crannies. So, assigning the matchsticks in a certain order—starting with the longest going towards shortest—may help.

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        peri = sum(matchsticks)
        expected_side, extra = divmod(peri, 4)
        if extra:
            return False
        if max(matchsticks) > expected_side:
            return False

        sides = [0] * 4
        def can_make(i):
            nonlocal sides, expected_side
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3]

            for j in range(4):
                if sides[j] + matchsticks[i] > expected_side:
                    continue
                sides[j] += matchsticks[i]
                if can_make(i + 1):
                    return True
                sides[j] -= matchsticks[i]

            return False

        matchsticks.sort(reverse=True)
        return can_make(0)

tanvirdotzaman

Leave a comment