Matchsticks to Square

这道题对小细节的减枝优化特别高，所以说思路虽然很容易出来，但是因为优化不够就会超时，这种问题吧，一般也没什么办法，人一旦形成一种明明可行但是却无法达到时间要求的思路一般都会在本思路的基础上加以改进而不是去想一个新办法，而这道题，想要利用回溯法AC，有两个必须实现的关键点，这里先放自己利用哈希表保存值次数的方法，这种思路是正确的，但是效率不高，会TLE

class Solution(object):
    def makesquare(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        base = sum(nums)
        if base % 4:
            return False

        return self.helper(collections.Counter(nums), 0, base / 4, 0, 4)

    def helper(self, nums, tmp, singleLen, time, limit):
        if tmp == 0 and time == limit:
            return True

        for key, value in nums.iteritems():
            if tmp + key < singleLen:
                nums[key] -= 1
                if nums[key] == 0:
                    nums.pop(key)
                if self.helper(nums, tmp + key, singleLen, time, limit):
                    return True
                nums[key] += 1
            elif tmp + key == singleLen:
                nums[key] -= 1
                if nums[key] == 0:
                    nums.pop(key)
                if self.helper(nums, 0, singleLen, time + 1, limit):
                    return True
                nums[key] += 1

        return False

接着上面说的，这两个关键点就是上面这个代码没有实现的，即首先将数组倒排序，因为如果一开始的值很大一个元素就超过了单边长，我们可以马上退出避免无谓计算，而第二点更加重要的就是，不要利用上面代码中的每条边逐个凑齐的思维，也就是说，每次遍历到一个元素，不要去在意它能不能构成当前这个边，而应该同时在四条边中扫描，看是否有任何一条边能够容纳这个元素，只要有，放进对应边中即可，这样我们就可以沿着数组顺序一个个解决问题而不会在中途跳过某个元素而在之后又返回来检查它，这就是这道题的关键，即四条边同时进行搜索

class Solution(object):
    def makesquare(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 4:
            return False

        base = sum(nums)
        if base % 4:
            return False

        nums.sort(reverse=True)
        target = [base / 4] * 4
        return self.helper(target, 0, len(nums), nums)

    def helper(self, target, start, end, nums):
        if start == end:
            return True

        for i in xrange(4):
            if target[i] - nums[start] >= 0:
                target[i] -= nums[start]
                if self.helper(target, start + 1, end, nums):
                    return True
                target[i] += nums[start]

        return False

另外还有DP加bit位的方法，不研究了