Python DFS solution


  • 5
    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
    

  • 0
    R

    @brotherhuang can someone please explain what's going on in dfs definition?


  • 0
    B

    @rizwan it start with the target length for 4 edges. For each num, try to remove it from one of the edge that is large than the number value. It will stop when it goes to the end of the num list.


Log in to reply
 

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