Matchsticks to Square

Intuition

Solution

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        """
        side: sum(nums) // 4
        visited: bool
        index: 0 to len(nums) - 1, when s equals to side, set it to 0
        """
        if not nums:
            return False
        nums.sort(reverse=True)

        side = sum(nums) / 4
        if int(side) != side:
            return False
        side = int(side)

        visited = [False] * len(nums)
        return self._dfs(nums, side, visited, 0, 0)

    @classmethod
    def _dfs(cls, nums, side, visited, index, length):
        if False not in visited:
            return length == 0

        if index >= len(nums):
            return False

        for i in range(index, len(nums)):
            if visited[i]:
                continue
            if length + nums[i] > side:
                continue
            if length + nums[i] == side:
                visited[i] = True
                if cls._dfs(nums, side, visited, 0, 0):
                    return True
            else:
                visited[i] = True
                if cls._dfs(nums, side, visited, i+1, length + nums[i]):
                    return True
                visited[i] = False
        return False