Home/

...

/

Minimum Subset Sum Difference (hard)

Minimum Subset Sum Difference (hard)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Minimum Subset Sum Difference (hard) lesson using Top-down Dynamic Programming with Memoization approach:

Press + to interact
Python 3.5
def can_partition(num):
  s = sum(num)
  dp = [[-1 for x in range(s+1)] for y in range(len(num))]
  return can_partition_recursive(dp, num, 0, 0, 0)
def can_partition_recursive(dp, num, currentIndex, sum1, sum2):
  # base check
  if currentIndex == len(num):
    return abs(sum1 - sum2)
  # check if we have not already processed similar problem
  if dp[currentIndex][sum1] == -1:
    # recursive call after including the number at the currentIndex in the first set
    diff1 = can_partition_recursive(
      dp, num, currentIndex + 1, sum1 + num[currentIndex], sum2)
    # recursive call after including the number at the currentIndex in the second set
    diff2 = can_partition_recursive(
      dp, num, currentIndex + 1, sum1, sum2 + num[currentIndex])
    dp[currentIndex][sum1] = min(diff1, diff2)
  return dp[currentIndex][sum1]
def main():
  print("Can partition: " + str(can_partition([1, 2, 3, 9])))
  print("Can partition: " + str(can_partition([1, 2, 7, 1, 5])))
  print("Can partition: " + str(can_partition([1, 3, 100, 4])))
main()

Students may be encouraged to complete the dry-run with this input:

Sample input #1

num:[1,2,3]

Recursive Call

currentIndex

sum1

sum2

diff1

diff2

Sets:

can_partition([1,2,3]

-

-

-

-

-

-

can_partition_recursive()

0

0

0

-

-

Set1: {} Set2: {1,2,3}

can_partition_recursive()

1

1

0

-

-

Set1: {1} Set2: {2,3}

can_partition_recursive()

2

3

0

-

-

Set1: {1,2} Set2: {3}

can_partition_recursive()

3

6

0

-

-

Set1: {1,2,3} Set2: {}

-

2

3

0

6

-

Set1: {1,2} Set2: {3}

can_partition_recursive()

3

3

3

-

-

Set1: {1,2,3} Set2: {}

-

2

3

0

6

0

Set1: {1,2} Set2: {3}

...

...

...

...

...

...

...

Sample input #2

Students may be encouraged to complete the dry-run with this input:

num:[1, 2, 3,9]

Recursive Call

currentIndex

sum1

sum2

diff1

diff2

Sets

can_partition([1,2,3,9])

-

-

-

-

-

-

can_partition_recursive()

0

0

0

-

-

Set1: {} Set2: {1,2,3,9}

can_partition_recursive()

1

1

0

-

-

Set1: {1} Set2: {2,3,9}

can_partition_recursive()

2

3

0

-

-

Set1: {1,2} Set2: {3,9}

can_partition_recursive()

3

6

0

-

-

Set1: {1,2,3} Set2: {9}

can_partition_recursive()

4

15

0

-

-

Set1: {1,2,3,9} Set2: {}

-

3

6

0

15

-

Set1: {1,2,3} Set2: {9}

...

...

...

...

...

...

...

Step-by-step solution construction

The solution has two main steps:

  1. Add a number to the first set and get the difference of the sum of two subsets.

  2. Add the same number to the second set and get the difference of the sum of two subsets.

For step 1, to compute the sum of the first set, we make a recursive call by adding the num[current_index] to sum1 (lines 16-17).

For step 2, to compute the sum of the second set, we make a recursive call by adding the num[current_index] to sum2 ( lines 21-22)

The base case is reached when the whole array has been traversed by one of the sets. At this point, we will return the difference of the sum of the current subsets (line 11-12)

The method returns the minimum of the two sums of the subsets at line 25.

Press + to interact
Python 3.5
def can_partition(num):
  s = sum(num)
  return can_partition_recursive(num, 0, 0, 0)
def can_partition_recursive(num, current_index, sum1, sum2):
  print("\t"*current_index,"current_index:",current_index)
  print("\t"*current_index,"sum1:",sum1)
  print("\t"*current_index,"sum2:",sum2)
  # base check
  if current_index == len(num):
    return abs(sum1 - sum2)
 
  # recursive call after including the number at the current_index in the first set
  diff1 = can_partition_recursive(
    num, current_index + 1, sum1 + num[current_index], sum2)
  print("\t"*current_index,"diff1 at index", current_index, "is:",diff1)
  # recursive call after including the number at the current_index in the second set
  diff2 = can_partition_recursive(
    num, current_index + 1, sum1, sum2 + num[current_index])
  print("\t"*current_index,"diff2 at index:", current_index, "is:", diff2)
  print("\t"*current_index,"min(",diff1,", ",diff2,") = ", min(diff1,diff2), sep="")
  return min(diff1, diff2)
def print_sets(current_index,num):
  
  print("\t"*current_index, "Processed elements: {",end="")
  for i in range(current_index):
      if(i != current_index-1):
        print(num[i],end=",")
      else:
        print(num[i],end="")
  print("}",end=" ")
  print("Remaining elements: {",end="")
  for i in range(current_index,len(num)):
    if(i != len(num)-1):
        print(num[i],end=",")
    else:
      print(num[i],end="")
  print("}")       
def main():
  arrs = [[1,2,3],[1, 2, 3,9],[1, 2, 7, 1, 5],[1, 3, 100, 4]]
  for arr in arrs:
    print("Finding paritition with minimum difference of subset sums for: ",arr)
    result = can_partition(arr)
    print("The array can be partitioned into two subsets with minimum difference of subset sums:",result)
    print("-"*100+"\n")
  
main()

Let’s update the solution to make use of memoization.

In the code below, on line 3, we initialize the matrix dp to size sum(num) x len(num) where sum(num) is the sum of numbers in the original array num.

To store the results in dp, we store the min(diff1,diff2) in dp[current_index][sum1] at line 28.

To utilize the existing result for a particular sum, we add the if condition on line 17. We process the sets only if we don’t find a previous sum against the current number.

Note: The function print_matrix has been added to print the matrix dp that stores the profits already calculated. This function does not contribute to the solution itself.

Press + to interact
Python 3.5
def can_partition(num):
  s = sum(num)
  dp = [[-1 for x in range(s+1)] for y in range(len(num))]
  print_matrix(dp, 0, num)
  return can_partition_recursive(dp, num, 0, 0, 0)
def can_partition_recursive(dp, num, current_index, sum1, sum2):
  print("\t"*current_index,"current_index:",current_index)
  print("\t"*current_index,"sum1:",sum1)
  print("\t"*current_index,"sum2:",sum2)
  # base check
  if current_index == len(num):
    return abs(sum1 - sum2)
  # check if we have not already processed similar problem
  if dp[current_index][sum1] == -1:
    # recursive call after including the number at the current_index in the first set
    diff1 = can_partition_recursive(
      dp, num, current_index + 1, sum1 + num[current_index], sum2)
    print("\t"*current_index, "diff1 at index", current_index, "is:", diff1)
    # recursive call after including the number at the current_index in the second set
    diff2 = can_partition_recursive(
      dp, num, current_index + 1, sum1, sum2 + num[current_index])
    print("\t"*current_index, "diff2 at index", current_index, "is:", diff2)
    print("\t"*current_index,"min(",diff1,", ",diff2,") = ",  min(diff1,diff2), sep="")
    dp[current_index][sum1] = min(diff1, diff2)
    print_matrix(dp, current_index, num)
  return dp[current_index][sum1]
def print_sets(current_index,num):
  
  print("\t"*current_index, "Processed elements: {",end="")
  for i in range(current_index):
      if(i != current_index-1):
        print(num[i],end=",")
      else:
        print(num[i],end="")
  print("}",end=" ")
  print("Remaining elements: {",end="")
  for i in range(current_index,len(num)):
    if(i != len(num)-1):
        print(num[i],end=",")
    else:
      print(num[i],end="")
  print("}")       
def print_matrix(dp, current_index, num):
  print("\t"*current_index, "dp:")
  print("\t"*current_index, " "*10, end=" ")
  for k in range(len(dp[0])):
    print(k, end="   ")
  print()
 
  print("\t"*current_index, "-"*( 10+(4*len(dp[0])) ) )
 
  for i in range(len(dp)):
    print("\t"*current_index, " [", i, "]: ", num[i], sep="", end= "  | ")
    for j in range(len(dp[i])):
      if j == (len(dp[i])-1):
        if dp[i][j]<0 or dp[i][j]>9:
          print(dp[i][j])
        else:
          print ("",dp[i][j])
      else:
        if dp[i][j]<0 or dp[i][j]>9:
          print(dp[i][j], end="  ")
        else:
          print ("", dp[i][j], end="  ")
  print("")
def main():
  arrs = [[1,2,3],[1, 2, 3,9],[1, 2, 7, 1, 5],[1, 3, 100, 4]]
  for arr in arrs:
    print("Finding paritition with minimum difference of subset sums for: ",arr)
    result = can_partition(arr)
    print("The array can be partitioned into two subsets with minimum difference of subset sums:",result)
    print("-"*100+"\n")
  
main()