###### tags: `Leetcode` `medium` `dfs` `backtracking` `python`

# 473. Matchsticks to Square

## [題目來源:] https://leetcode.com/problems/matchsticks-to-square/

## 題目:
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.


#### [圖片來源:] https://leetcode.com/problems/matchsticks-to-square/

## 解題思路:
題目為: **能否把數組分成4組，每組和都相同**

* 使用回朔法: **BackTracking**
[backtracking介紹]https://haogroot.com/2020/09/21/backtracking-leetcode/
* 先設好4條邊
* 需先將matchsticks數組由大到小排好
* 逐一將每條火柴看是否能放入其中一條邊中
* 若可以則繼續遍歷，直到所有火柴都能放入

## Python:

class Solution(object):
    def makesquare(self, matchsticks):
        """
        :type matchsticks: List[int]
        :rtype: bool
        """
        #backtracking: 回朔
        #init
        if not matchsticks or len(matchsticks)<4:
            return False
        div,mod=divmod(sum(matchsticks),4)
        if mod!=0 or max(matchsticks)>div:
            return False
        #由大到小排好 先讓大的去填滿
        matchsticks.sort(reverse=True)
        #4條邊最大可容納div
        target=[div]*4
        return self.dfs(matchsticks,0,target)
    def dfs(self,matchsticks,pos,target):
        if pos==len(matchsticks):
            return True
        val=matchsticks[pos]
        #4條邊
        for i in range(4):
            if target[i]>=val:
                target[i]-=val
                #往後遞迴，確認後面還能繼續擺
                if self.dfs(matchsticks,pos+1,target):
                    return True
                #代表後面無法擺完 所以此位置不能放當前val
                target[i]+=val
            #加此行優化 避免time limit exceeded
            if pos==0:
                return False
        return False

result=Solution()
ans=result.makesquare(matchsticks=[14,10,10,10,10,10,10,10,10,10,10,10,8,9,19])

print(ans)