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