Matchsticks to Square

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

Input: [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: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

The length sum of the given matchsticks is in the range of 0 to 10^9.

The length of the given matchstick array will not exceed 15.

分析一下，要拼成一个正方形，意味着把输入均分为4等份，每份数字的和是相等的，且不用把数字拆开。根据该问题的一个讨论描述：

划分数字问题，也就是把正整数集S分为两个子集S1和S2，使得S1与S2的和相等，这个划分问题是NP完全的。但是考虑到问题的限制，数字和在0到10^9，每个数字不超过15，说明问题不会很大，所以，可以尝试DFS。

我们把原始DFS问题中的距离理解为数字大小，用达成目标值（一条边长度）所需要的数字大小作为是否可达的条件。这样我们就可以借助DFS思想来写代码，这里是一个python的代码（来源，做了一点改动），可读性比较好：

def makesquare(nums):
    
    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)
    if numSum % 4 != 0: 
        return False
    
    nums.sort(reverse=True)
    target = [numSum/4] * 4;
    return dfs(nums,0, target)

我们来分析这个代码，先跳过dfs的函数看主逻辑，做一些判断，如果数字数量小于4或数字和不能被4整除肯定是False，为了让整个程序的判断更快，把输入做了排序，这个操作的解释是（依然来源于上面的讨论）：

把输入从大到小排序可以让程序更快，这背后的原因是我们总是尝试把下一个数字放到我们的四条边中，如果问题本身没有解，那么先尝试大的数字会更快地得到这个结论。

然后target是四条边的长度，也就是把数字分成四份后每份的数字和，这样我们可以对每份记录是否达到了我们需要的数字。最后看dfs，可以看到dfs接受3个参数，第一个是传入的所有数字num，第二个是当前我们要处理数字的位置pos，第三个是目标值target，也就是前面说的四条边的值。

进入dfs每次我们判断如果位置pos已经达到了num的长度，那么已经结束了，走到这里说明原来的条件都满足，结果就是True。然后是4条边的遍历，如果每条边的余量target能够容纳当前数字，那么把当前数字归入这条边，然后继续dfs递归。如果递归结果为True，说明这个方法行得通，可以返回True了，否则就放弃容纳这个数，让下一条边来继续处理，这个逻辑可以递归到所有的情况。这样我们就可以完成所有的判断了。

值得注意的是，这里dfs能成功的关键因素是我们的问题规模比较小，如果问题很大，求解也是很困难的。

但是这个解法提交的时候，发现对于输入[12,12,12,12,12,12,12,12,12,12,12,12,12]超时，所以我加了讲个判断条件：

if max(nums) > numSum / 4: 
    return False
if len(set(nums)) == 1 and len(nums) % 4 != 0: 
    return False

第一个是如果最大值比一条边长，肯定不行，如果所有的值都一样，但是数目不能被4整除，也不行，这样就通过了测试。