Leetcode 473. Matchsticks to Square

Problem

Leetcode 473 - Matchsticks to Square

Example:

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.

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Approach

We can solve this problem using DFS and sorting. First sort first, then we can use greedy approach and put each side into array as long as the side’s length doesn’t go over the total of matchsticks / 4.

Here is the Python code for the solution:

class Solution:
        def makesquare(self, matchsticks: List[int]) -> bool:
        matchsticks.sort(reverse=True)
        total = 0
        for i in range(len(matchsticks)):
            total += matchsticks[i]
        
        side = total / 4
        sides = [0] * 4
        
        def dfs(i):
            if i == len(matchsticks):
                return True
            
            for s in range(4):
                if sides[s] + matchsticks[i] <= side:
                    sides[s] += matchsticks[i]
                    if dfs(i+1):
                        return True
                    sides[s] -= matchsticks[i]
                
                if sides[s] == 0:
                    break
            
            return False
        return dfs(0) 
    

Time Complexity and Space Complexity

Time Complexity: $O(4^n)$

Space Complexity: $O(n)$