Solutions

1. Backtracking (Brute Force)

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        if sum(matchsticks) % 4 != 0:
            return False

        sides = [0] * 4

        def dfs(i):
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3]

            for side in range(4):
                sides[side] += matchsticks[i]
                if dfs(i + 1):
                    return True
                sides[side] -= matchsticks[i]

            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(4 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Backtracking (Pruning)

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)
        if total_length % 4 != 0:
            return False

        length = total_length // 4
        sides = [0] * 4
        matchsticks.sort(reverse=True)

        def dfs(i):
            if i == len(matchsticks):
                return True

            for side in range(4):
                if sides[side] + matchsticks[i] <= length:
                    sides[side] += matchsticks[i]
                    if dfs(i + 1):
                        return True
                    sides[side] -= matchsticks[i]

                if sides[side] == 0:
                    break

            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(4 ^ n)$
Space complexity: $O(n)$ for recursion stack.

3. Dynamic Programming (Bit Mask)

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)
        if total_length % 4 != 0:
            return False

        length = total_length // 4
        if max(matchsticks) > length:
            return False

        n = len(matchsticks)
        dp = [float("-inf")] * (1 << n)
        matchsticks.sort(reverse=True)

        def dfs(mask):
            if mask == 0:
                return 0
            if dp[mask] != float("-inf"):
                return dp[mask]

            for i in range(n):
                if mask & (1 << i):
                    res = dfs(mask ^ (1 << i))
                    if res >= 0 and res + matchsticks[i] <= length:
                        dp[mask] = (res + matchsticks[i]) % length
                        return dp[mask]
                    if mask == (1 << n) - 1:
                        dp[mask] = -1
                        return -1

            dp[mask] = -1
            return -1

        return not dfs((1 << n) - 1)

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(n + 2 ^ n)$