# 416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

# Solution

Approach 1: recursion/backtracking.

Approach 2: DP using a 2D array.

# Code (Python)

Approach 1:

    def canPartition1(self, nums: List[int]) -> bool:
        total = sum(nums)
        if sum(nums) % 2 == 1 or len(nums) == 1 or max(nums) > total / 2:
            return False
        nums.sort(reverse=True) # trick to glob the bigger chunks early
        # recursion/backtracking
        return self._can_sum_to(0, nums, total / 2)
    
    def _can_sum_to(self, start, nums, total):
        if start >= len(nums) or total < 0: # where nums[start] > total is not a False condition because the following nums are less than nums[start]
            return False
        elif nums[start] == total or total == 0:
            return True
        new_start = start + 1 # careful for new_start out of index range
        while new_start < len(nums) and nums[new_start] == nums[start]:
            new_start += 1
        return (self._can_sum_to(start + 1, nums, total - nums[start]) or
                self._can_sum_to(new_start, nums, total))

Approach 2:

    def canPartition(self, nums):
        # DP: LTE for a single test case but otherwise it should work
        total = sum(nums)
        if sum(nums) % 2 == 1 or len(nums) == 1 or max(nums) > total / 2:
            return False
        nums.sort(reverse=True)
        # can_do[i][j] -- nums[:i+1] contains a subset that sums up to j
        # transfer: can_do[i][j] = can_do[i-1][j] or can_do[i-1][j-nums[i]]
        can_do = [[False for j in range(total // 2 + 1)] for i in range(len(nums))]
        for i in range(len(nums)):
            can_do[i][0] == True
            for j in range(total // 2 + 1):
                if i == 0:
                    can_do[0][j] = (nums[0] == j or j == 0)
                else:
                    can_do[i][j] = can_do[i-1][j]
                    if j - nums[i] >= 0:
                        can_do[i][j] = can_do[i][j] or can_do[i-1][j-nums[i]]
        return can_do[-1][-1]

# Code (C++)

Approach 1:

Approach 2: