Same idea, add used set to avoid some duplicated search.
def makesquare(self, nums):
:type nums: List[int]
if len(nums) < 4:
total = sum(nums)
if total % 4 != 0:
target = total / 4
if any(n > target for n in nums):
return self.dfs([target] * 4, 0, nums)
def dfs(self, lefts, idx, nums):
if idx == len(nums):
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):
lefts[i] += n
@bhavik92 My bad, I should not to try to illustrate it concisely with at the cost of clarity. Let's try the last time. In the process of DFS (or backtracking), we process each case without knowing the future case.
Now we need a certain length L, and have two options: 1) a (len(a) == L); and 2) b+c (len(b) + len(c) == L).
After this step, we remove either a or (b and c) from the original array. Then we may need to deal with the remain stick(s) in three conditions:
a) a case requires length of L;
b) a case asks for len(b) and another case needs len(c);
c) none of above.
If we initially applied option 1), then we can deal with case a) and b); if we used option 2), we can only deal with case b), which may result in rejecting a true answer. For condition c), either option won't work, therefore, we would correctly reject a false answer.