Please correct OJ's DP solution (try [1, 3, 4, 4])

  • 0

    Test case [1, 3, 4, 4] should return False, but I tried it as custom test case and OJ said "Expected answer is true". So, I am guessing OJ's DP solution is kind of like @SergeyTachenov 's solution. Here is my Python corrected version based on @SergeyTachenov 's one:

    class Solution(object):
        def canPartition(self, nums):
            if not nums or len(nums) < 2:
                return False
            total = sum(nums)
            if total & 1:
                return False
            target, n, max_v = total >> 1, len(nums), 0
            line = [True] + [False] * target
            for d in nums:
                if d > target:
                    return False
                for v in xrange(min(max_v, target-d), -1, -1):
                    if line[v]:
                        line[v+d] = True
                        max_v = max(max_v, v+d)
                    if line[target]:
                        return True
            return False

    The key point is that in the inner loop, if we want to modify the array on the fly, we should do it backwards. Otherwise, line[v+x*d] are all True where x is 1, 2, 3,....

Log in to reply

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