Python Explanation

  • 3

    If the sum isn't divisible by 4, or if there are less than 4 matchsticks, or if one matchstick is greater than the expected sidelength, then it is impossible.

    Otherwise, let's see if it is possible to partition the set into 4 equal parts. We do this by bitmask dp. Let the i-th position of mask be 1 if we have not used A[i] yet, and let cur represent the length of an unfilled sidelength we have yet to fill.


    if len(A) < 4 or sum(A) % 4 or max(A) > sum(A) / 4:
      return False
    T = sum(A) / 4
    N = len(A)
    memo = {}
    def dp(mask, cur = T):
      if (mask, cur) in memo: return memo[mask, cur]
      if mask == 0: return cur == 0
      if cur == 0: return dp(mask, T)
      ans = False
      for bit in xrange(N):
        if mask & (1 << bit):
          if A[bit] > cur:
          if dp(mask ^ (1 << bit), cur - A[bit]):
            ans = True
      memo[mask, cur] = ans
      return ans
    return dp(2**N - 1)

  • 0

    Can you please explain the line:
    if cur == 0: return dp(mask, T)

  • 0

    When we finished building one side of the square, cur (the remaining length of a side of the square we are building) will be 0. We then reset it back to T.

  • 0

    I think maybe using only 'mask' as the key instead of '(mask, cur)' is enough.

Log in to reply

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