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)
In the terminating condition when we reach : pos==len(nums),
why don't we need to check if all 4 targets have been filled?
@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
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
@brotherhuang can someone please explain what's going on in dfs definition?
@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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.