# 473. Matchsticks to Square

#### Medium

***

You are given an integer array `matchsticks` where `matchsticks[i]` is the length of the `ith` matchstick. You want to use **all the matchsticks** to make one square. You **should not break** any stick, but you can link them up, and each matchstick must be used **exactly one time**.

Return `true` if you can make this square and `false` otherwise.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg)

```
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.
```

**Example 2:**

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

 

**Constraints:**

* `1 <= matchsticks.length <= 15`
* `1 <= matchsticks[i] <= 108`

```python
class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        total = sum(nums)
        target = total // 4
        nums.sort(reverse=True)
        if total % 4 != 0:
            return False
        return self.dfs(nums, [target]*4, 0)
        
    def dfs(self, nums, target, index):
        if index == len(nums):
            return target[0] == 0 and target[1] == 0 and target[2] == 0 and target[3] == 0
        for i in range(4):
            if nums[index] > target[i]:
                continue
            target[i] -= nums[index]
            if self.dfs(nums, target, index+1):
                return True
            target[i] += nums[index]
        return False
```