Python DFS solution


  • 3
    B
    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            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)
            nums.sort(reverse=True)
            if numSum % 4 != 0: return False
            target = [numSum/4] * 4;
            return dfs(nums,0, target)
    

  • 0
    P

    In the terminating condition when we reach : pos==len(nums),

    why don't we need to check if all 4 targets have been filled?


  • 0
    L

    @protein.graph because we never could have gotten to the end unless everything was filled or it would've failed before we even got to dfs


  • 0
    V

    Why need "target[i] += nums[pos]" ?


  • 0
    S

    Same idea, add used set to avoid some duplicated search.

    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            nums.sort(reverse=True)
            if len(nums) < 4:
                return False
            total = sum(nums)
            if total % 4 != 0:
                return False
            target = total / 4
            if any(n > target for n in nums):
                return False
            return self.dfs([target] * 4, 0, nums)
    
        def dfs(self, lefts, idx, nums):
            if idx == len(nums):
                return True
            n = nums[idx]
            used = set()
            for i, left in enumerate(lefts):
                if left >= n and left not in used:
                    lefts[i] -= n
                    if self.dfs(lefts, idx + 1, nums):
                        return True
                    lefts[i] += n
                    used.add(left)
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.