Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Subset Sum

Problem Statement

Example 1:

Example 2:

Example 3:

Try it yourself

Problem Statement

Given a set of positive numbers, determine if there exists a subset whose sum is equal to a given number 'S'.

Example 1:

Input: {1, 2, 3, 7}, S=6
Output: True
The given set has a subset whose sum is '6': {1, 2, 3}

Example 2:

Input: {1, 2, 7, 1, 5}, S=10
Output: True
The given set has a subset whose sum is '10': {1, 2, 7}

Example 3:

Input: {1, 3, 4, 8}, S=6
Output: False
The given set does not have any subset whose sum is equal to '6'.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
S

Shan

· 4 years ago

It should be more clearly stated this problem is EXACTLY like the previous problem equal partition, the only difference is S is provided in this problem and in the previous problem is is calculated (sum(arr) / 2).

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def canPartition(self, num, total_sum):
    
    def solve(index, acc, memo):
      
      if index in memo and acc in memo[index]:
        return memo[index][acc]

      if acc == total_sum:
        return True 

      if index == len(num) and acc != total_sum:
        return False
        
      result = solve(index + 1, acc + num[index], memo) or solve(index + 1, acc, memo)

      if index not in memo:
        memo[index] = {}

      memo[index][acc] = result

      return result

    return solve(0, 0, {})
A

abhi.newgbu1185

· 2 months ago

Lastly written code is also of SC=O(N*S) and not of O(S). I think here we do like we did in i%2 and i-1%2 we did in 0-1 knaposack

On This Page

Problem Statement

Example 1:

Example 2:

Example 3:

Try it yourself