Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Equal Subset Sum Partition

Problem Statement

Try it yourself

Problem Statement

Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.

Example 1:

Input: {1, 2, 3, 4}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 4} & {2, 3}

Example 2:

Input: {1, 1, 3, 4, 7}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 3, 4} & {1, 7}

Example 3:

Input: {2, 3, 4, 6}
Output: False
Explanation: The given set cannot be partitioned into two subsets with equal sum.

Constraints:

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

Try it yourself

This problem looks similar to the 0/1 Knapsack problem, try solving it before moving on to see the solution:

Python3
Python3
. . . .
Saurav Ghosh

Saurav Ghosh

· 4 months ago


```python
def equal_subset_exists(arr):
    total = sum(arr)

    if total % 2 != 0:
        return False

    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True # BASE CASE

    for i in range(len(arr)):
        for j in range(target, arr[i]-1, -1):

            # CORE IDEA j = (previous sum) + current number
            # REWRITTEN as previous sum = j - current number
            if dp[j - arr[i]]:
                dp[j] = True

            if dp[target]:
                return True

    return dp[target]
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def canPartition(self, num):
    
    def solve(left, right, index, memo):
      # return from memo
      if index in memo and (str(left) + str(right)) in memo[index]:
        return memo[index][(str(left) + str(right))]
      
      # we reached the end
      if index == len(num):
        return False
      
      # we find equality
      if left == right:
        return True

      left_without = left - num[index]
      right_with = right + num[index]

      result = solve(left, right, index + 1, memo) or solve(left_without, right_with, index + 1, memo)
      
      if index not in memo:
        memo[index] = {}

      memo[index][(str(left) + str(right))] = result
      return result

    return solve(sum(num), 0, 0, {})
D

danielsadac

· 4 years ago

I think the python solution is not correct, it uses sum when it's a reserved keyword.

Show 1 reply
H

Hyuntae Kim

· 4 years ago

I really like the way you explain the answers in both ways (top-down and bottom-up) But have one question, we can choose one of them right? is there any kind of cases we should approach it with certain way?

A

Alex Hansen

· 4 years ago

Does this only work for sorted arrays?

Show 1 reply
L

Learner

· 5 years ago

Is there any way to get a refund? I really don't think the way this course is designed is for me...

Show 2 replies

Reading Progress

0%

On This Page

Problem Statement

Try it yourself