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

• 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,....

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