# LC 416. Partition Equal Subset Sum

### [Problem link](https://leetcode.com/problems/partition-equal-subset-sum/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

Given an integer array <code>nums</code>, return <code>true</code> if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or <code>false</code> otherwise.

**Example 1:**

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

**Example 2:**

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

**Constraints:**

- <code>1 <= nums.length <= 200</code>
- <code>1 <= nums[i] <= 100</code>

## Solution 1 - Backtracking(TLE)
#### Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False

        def backtrack(startIdx, tmp_sum):
            if startIdx == len(nums):
                return False
            if tmp_sum == total // 2:
                return True

            for i in range(startIdx, len(nums)):
                if tmp_sum > total // 2:
                    return False
                tmp_sum += nums[i]
                if backtrack(i + 1, tmp_sum):
                    return True
                tmp_sum -= nums[i]

        return backtrack(0, 0)

## Solution 2 - DP(2D)
#### Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2:
            return False

        target = target >> 1

        row = len(nums)
        col = target + 1

        dp = [[0 for _ in range(col)] for _ in range(row)]

        # initial dp
        for i in range(1, target):
            if nums[0] <= i:
                dp[0][i] = nums[0]

        for i in range(1, row):
            cur_weight = nums[i]
            cur_val = nums[i]
            for j in range(1, col):
                if cur_weight > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val)

        return dp[-1][-1] == target

## Solution 3 - DP(1D)
#### Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2:
            return False

        target = target >> 1
        dp = [0] * (target + 1)

        for i in range(len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

        return dp[-1] == target

#### C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2) {
            return false;
        }
        int target = sum / 2;

        vector<int> dp(target + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
};

>### Complexity
>n = nums.length
>m = int(sum(nums[i]) / 2)
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($2^n$) | O(n) |
>| Solution 2 | O(mn) | O(mn) |
>| Solution 3 | O(mn) | O(m) |

## Note
[ref](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.md)