# Python 2 Clean DP Solutions Comparison w/ inline comment explanation

• Faster/More efficient method. Less intuitive, relies on weird method of going through weights in reverse on the inner loop to avoid overwriting prior outer loop iteration's dp[j] calculations.

``````class Solution(object):
# this is an application of knapsack problem, where w=sum(nums)/2
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
isum = sum(nums)

# if weight not divisible by two, we cannot possibly have two equal sets
if isum % 2 != 0:
return False

# isum is weight
isum /= 2

# dp init
dp = [False for j in xrange(isum + 1)]
dp[0] = True

# j is weight bound, and i is arr pointer.
# dp[j] :: for a weight j, can we partition into two equal sets with elements 0..i
for i in xrange(len(nums)):
# reversal neessary, because if we go in non-reversed order, we will overwrite
# dp[] calculations from the previous iteration of outer loop. thus we go small to big to preserve previous iteration
for j in reversed(xrange(1, isum + 1)):
if j - nums[i] >= 0:
dp[j] = dp[j] or dp[j - nums[i]]

return dp[isum]

``````

Slightly less efficient, still same complexity at O(n^2)... More intuitive and straight forward in my opinion. This i my preferred solution.

``````class Solution(object):
# this is an application of knapsack problem, where w=sum(nums)/2
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
isum = sum(nums)

# if weight not divisible by two, we cannot possibly have two equal sets
if isum % 2 != 0:
return False

# isum is weight
isum /= 2

# dp init
dp = [[False for j in xrange(isum + 1)] for i in xrange(len(nums) + 1)]

for i in xrange(len(nums) + 1):
for j in xrange(isum + 1):
if i == 0 and j == 0: # base case, nothing to select with, and 0 weight
dp[i][j] = True
elif i == 0: # i == 0 signifies base case where we select nothing, we can never achieve any non-zero goal
dp[i][j] = False
elif j == 0: # we can always achieve weight goal of 0, just select nothing.
dp[i][j] = True
else: # dp transition step
if j >= nums[i - 1]: # do a weight bounds check, then check both possibilities of both including and excluding the current element nums[i - 1]
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
else:
dp[i][j] = dp[i - 1][j]

return dp[len(nums)][isum]

``````

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