# 416-partition-equal-subset-sum


Try it on <a href='https://leetcode.com/problems/416-partition-equal-subset-sum'>leetcode</a>

## Description
<div class="description">
<div><p>Given a <strong>non-empty</strong> array <code>nums</code> containing <strong>only positive integers</strong>, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.</p>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

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

<p><strong>Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
</ul>
</div>
</div>

## Solution(Python)
```Python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        return self.dynamicprogramming(nums)

    """
    Time complexity: O(2^n)
    Space Complexity: O(n)
    """

    def bruteforce(self, nums: List[int]) -> bool:
        n = len(nums)

        def recur(s1, s2, i):
            if i == n:
                return sum(s1) == sum(s2)

            left = recur(s1 + [nums[i]], s2, i + 1)
            right = recur(s1, s2 + [nums[i]], i + 1)

            return left or right

        return recur([], [], 0)

    """
    
    dp[i][j] = dp[i-1][j] || dp[i][j-nums[i]] if i th coin is used adding to j 
                    ^
                    |
                    if ith coin not used and considering i-1th coins 
    Time complexity: O(n*w)
    Space Complexity: O(w)
    """

    def dynamicprogramming(self, nums: List[int]) -> bool:
        if sum(nums) & 1:
            return False
        total = sum(nums) // 2
        n = len(nums)
        memo = {}

        def dfs(t, index):
            if t in memo:
                return memo[t]
            if t < 0:
                return 0
            elif t == 0:
                return 1
            for i in range(index, n):
                if dfs(t - nums[i], i + 1):
                    memo[t] = 1
                    return memo[t]
            memo[t] = 0
            return memo[t]

        ans = dfs(total, 0)
        return ans

```