416-partition-equal-subset-sum

Try it on leetcode

Description

Given a non-empty array nums 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.

 

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:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution(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