LeetCode 416. Partition Equal Subset Sum Explanation and Solution

Thanks in advance!

Two Solutions: backtracking and dynamic programming.

[abhaypatil]

One optimization is really helpful -
sort (nums.begin(), nums.end());
reverse (nums.begin(), nums.end());
This will ensure that "(target<0)" condition is hit as soon as possible for the wrong partitions.
I understand that this takes O(nlogn) time, but the savings on recursion calls is even huger.

[Saurabh]

what's the complexity of the first approach (backtracking/dfs) ? 2^N maybe?

[LV-eice]

I feel like most of the top dow approach is basically Backtracing and bottomup is 2D Table or 1D array

[xuejingtan]

I think your explanation is so good. However, I think for the first method. We shouldn't use a recursion function as the condition of if clause. But I don't know how to revise it. Can you think about it and make a revision on it?

[alinal]

can you explain sum /= 2; and target - nums[index]? What does these mean?

[sumantopal]

surprisingl the recursion approach performce better than the DP solution

[krystaljinluma]

The DP solution is too fast.. should've talked more about why start from j=sum and j--

[aunnfriends]

Both of your code fail with LTE for the following input from lintcode (not leetcode)
[1, 4, 5, 6, 1, 2, 4, 1, 3, 4, 1, 2, 4, 5, 1, 91, 4, 5, 6, 1, 2, 4, 1, 3, 4, 1, 2, 4, 5, 1]

Here is the Python code (not mine) which works for that input also

class Solution:
"""
@param nums: a non-empty array only positive integers
@return: true if can partition or false
"""
def canPartition(self, nums):
sum_nums = sum(nums)
if sum_nums % 2 == 1:
return False

nums.sort(reverse = True) # try largest nums first
target = sum_nums // 2

subset_sum = [True] + [False] * target

for num in nums:
for i in range(target - 1, -1, -1): # backwards so cannot use same num repeatedly
if subset_sum[i] and i + num <= target:
if i + num == target: # early return, solution found
return True
subset_sum[i + num] = True # mark this value

return False