473.md

Matchsticks to Square

Description

link

---

Solution

DFS，主要定义DFS函数的时候需要传入target数组，代表当前这个边的目标长度还剩多少，每次循环到一个新的pos，分别四次更新target值，直到满足为止

这里讲一下DFS的时间复杂度判断：如果是最坏情况的话，首先因为初始DFS的循环是O(M + N)，每个点的最大遍历长度是O(MN)，这就是最坏情况的时间复杂度

---

Code

最坏情况下的时间复杂度是O((M+N)*MN)，空间复杂度是O(MN)

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        def dfs(nums, pos, target):
            if pos == len(nums): return True
            for i in range(4):
                if target[i] >= nums[pos]:
                    target[i] -= nums[pos]
                    if dfs(nums, pos+1, target): return True
                    target[i] += nums[pos]
            return False
        if len(nums) < 4 : return False
        numSum = sum(nums)
        nums.sort(reverse=True)
        if numSum % 4 != 0: return False
        target = [numSum/4] * 4;
        return dfs(nums,0, target)