473. Matchsticks to Square

https://leetcode.com/problems/matchsticks-to-square/

Matchsticks to Square - LeetCode

 

2200ms !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

import collections
from functools import lru_cache

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        
        if not nums:
            return False
        if len(nums) < 4:
            return False
        
        nsum = sum(nums)
        
        side = int(nsum/4)
        
        nums = sorted(nums, reverse=True)
        
        @lru_cache(maxsize=None)
        def dfs(i, sides) -> bool:
            if i == len(nums):
                return sum(sides) == 0
            for si, side in enumerate(sides):
                if side-nums[i] >= 0:
                    _sides = sides[:si] + tuple([side-nums[i]]) + sides[si+1:]
                    if dfs(i+1, _sides):
                        return True
            return False
        
        return dfs(0, tuple([side]*4))

add pruning

500ms!!!!!!!!!!!!!!!

import collections
from functools import lru_cache

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        
        if not nums:
            return False
        if len(nums) < 4:
            return False
        
        nsum = sum(nums)
        #[!!!]
        if nsum%4 != 0:
            return False
        
        side = int(nsum/4)
        
        nums = sorted(nums, reverse=True)
        
        @lru_cache(maxsize=None)
        def dfs(i, sides) -> bool:
            if i == len(nums):
                return sum(sides) == 0
            for si, side in enumerate(sides):
                if side-nums[i] >= 0:
                    _sides = sides[:si] + tuple([side-nums[i]]) + sides[si+1:]
                    if dfs(i+1, _sides):
                        return True
            return False
        
        return dfs(0, tuple([side]*4))

32ms ????

property ; unique pairs

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        
        n = len(nums)
        nums = sorted(nums, reverse=True)
        
        s = sum(nums)
        
        if n < 4:
            return False
        if s % 4 != 0:
            return False
        
        target = s//4
        visited = [0 for i in range(n)]
        
        def dfs(nums, cur, i, target, n):
            if cur == target:
                return True
            for k in range(i+1, n):
                if not visited[k] and nums[k]+cur <= target:
                    visited[k] = True
                    if dfs(nums, cur + nums[k], k, target, n):
                        return True
                    visited[k] = False
            return False
        
        for i in range(n):
            if visited[i]:
                continue
            visited[i] = True
            if not dfs(nums, nums[i], i, target, n):
                return False
            
        return True