Home/

...

/

Problem Challenge 1

Problem Challenge 1

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 1 lesson using Top-down Dynamic Programming with Memoization appraoch:

Press + to interact
Python 3.5
def count_subsets(num, sum):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
  dp = [[-1 for x in range(sum+1)] for y in range(len(num))]
  return count_subsets_recursive(dp, num, sum, 0)
def count_subsets_recursive(dp, num, sum, currentIndex):
  # base checks
  if sum == 0:
    return 1
  n = len(num)
  if n == 0 or currentIndex >= n:
    return 0
  # check if we have not already processed a similar problem
  if dp[currentIndex][sum] == -1:
    # recursive call after choosing the number at the currentIndex
    # if the number at currentIndex exceeds the sum, we shouldn't process this
    sum1 = 0
    if num[currentIndex] <= sum:
      sum1 = count_subsets_recursive(
        dp, num, sum - num[currentIndex], currentIndex + 1)
    # recursive call after excluding the number at the currentIndex
    sum2 = count_subsets_recursive(dp, num, sum, currentIndex + 1)
    dp[currentIndex][sum] = sum1 + sum2
  return dp[currentIndex][sum]
def main():
  print("Total number of subsets " + str(count_subsets([1, 1, 2, 3], 4)))
  print("Total number of subsets: " + str(count_subsets([1, 2, 7, 1, 5], 9)))
main()

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

Sample input #1

num:[1,2,3]

Recursive Call

currentIndex

sum

sum1

sum2

Sets

count_subsets([1,1,2,3],4)

-

-

-

-

-

count_subsets_recursive

0

4

-

-

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

count_subsets_recursive

1

3

-

-

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

count_subsets_recursive

2

2

-

-

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

count_subsets_recursive

3

0

-

-

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

-

2

2

1

-

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

-

3

2

0

-

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

count_subsets_recursive

4

2



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

-

3

2

0

0

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

-

2

2

1

0

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

...

...

...

...

...

...

Sample input #2

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

num:[1, 2, 3,9]

Recursive Call

currentIndex

sum

sum1

sum2

Sets

count_subsets([1,1,2,3],4)

-


-

-

-

count_subsets_recursive

0

4

-

-

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

count_subsets_recursive

1

3

-

-

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

count_subsets_recursive

2

2

-

-

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

count_subsets_recursive

3

0

-

-

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

-

2

2

1

-

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

count_subsets_recursive

3

2

-

-

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

count_subsets_recursive

4

2

-

-

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

-

3

2

0

3

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

-

2

2

1

0

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

-

1

3

1

-

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

...

...

...

...

...

...

Step-by-step solution construction

We have three main parts of the solution:

  1. Writing the base conditions for the recursive code
  2. Recursively forming Sets in two alternative ways:
  • While including the number at the current index
  • While excluding the number of the current index
  1. Utilizing the count computed earlier for the given index

In the code below, on lines 16-23, we define the base conditions:

  • We return 1 as the count when the sum reaches 0, meaning that a subset whose sum equals sum does exist. This works because we subtract num[current_index] from sum while making each recursive call.

  • If we have exhausted the list and the sum is not yet 0, we return 0. We will be calling the function recursively by incrementing the current_index, so we will eventually get to the end of the num array.

On lines 28-36, we implement the second part of the solution:

  • On line 29, if the number at the current_index is less than the remaining sum, we issue the recursive command to count the subsets with the sum sum-num[current_index] in the array[current_index+1:end].

  • On line 36, we issue another recursive call to count the subsets with the sum, while excluding the number at the current_index.

To make it easier to follow the working of the program, we have added print statements to both the base conditions, printing out whether the subset currently being checked has the required sum or not. To support this, we have added a parameter, candidate_set, to the count_subsets_recursive function, and also introduced a global variable required_sum.

Press + to interact
Python 3.5
required_sum = 0
def count_subsets(num, sum):
  global required_sum 
  required_sum = sum
  return count_subsets_recursive(num, sum, 0, "")
def count_subsets_recursive(num, sum, current_index, candidate_set):
  print("\t"*current_index, "current_index:", current_index, end="")
  if current_index<len(num):
    print(", num[", current_index, "]: ", num[current_index], sep="")
  else:
    print(", end of input")
  print("\t"*current_index, "required sum:", sum)
  # print_sets(current_index,num)
  # base checks
  if sum == 0:
    print("\t"*current_index, "** Subset with required sum exists:", candidate_set[2:], "**")
    return 1
  n = len(num)
  if n == 0 or current_index >= n:
    print("\t"*current_index, " Sum of subset {", candidate_set[2:], "} does not equal required sum (", required_sum ,"), backtracking to explore other branches", sep="")
    return 0
  # recursive call while choosing the number at the current_index
  # if the number at current_index exceeds the remaining sum, we shouldn't proceed
  sum1 = 0
  if num[current_index] <= sum:
    sum1 = count_subsets_recursive(
      num, sum - num[current_index], current_index + 1, candidate_set + ", " + str(num[current_index]))
    print("\t"*current_index, "sum1 at index", current_index, "is:", sum1)
    if sum1>0:
      print("\t"*current_index, " included num[", current_index, "]: ", num[current_index], sep="")
  # recursive call while excluding the number at the current_index
  sum2 = count_subsets_recursive(num, sum, current_index + 1, candidate_set)
  print("\t"*current_index, "sum2 at index", current_index, "is:", sum2)
  if sum2>0:
    print("\t"*current_index, " excluded num[", current_index, "]: ", num[current_index], sep="")
  print("\t"*current_index," count of subsets at index ", current_index, " (sum1 + sum2: ", sum1, " + ", sum2, ") is: ", sum1+sum2, sep="")
  return sum1+sum2
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, 1, 2, 3], 4],[[1, 2, 7, 1, 5], 9]]
  for arr in arrs:
    print("Finding total number of subsets with sum",arr[1],"in:",arr[0])
    result = count_subsets(arr[0], arr[1])
    print("Subsets with sum",arr[1],"are:",result)
    print("-"*100+"\n")
main()

Let’s update the solution to make use of memoization. On line 6, we set up the two-dimensional matrix, dp, in which we will store the results of sub-problems for re-use. On line 46, we store the count of the subsets against the current values of current_index and sum in the dp matrix for later utilization.

On line 33, we check if we had previously calculated the count of subsets for the current input number and the remaining sum. If not, we issue the recursive calls for further processing.

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
required_sum = 0
def count_subsets(num, sum):
  global required_sum 
  required_sum = sum
  # create a two dimensional array for Memoization, each element is initialized to '-1'
  dp = [[-1 for x in range(sum+1)] for y in range(len(num))]
  print_matrix(dp, 0, num)
  return count_subsets_recursive(dp, num, sum, 0, "")
def count_subsets_recursive(dp, num, sum, current_index, candidate_set):
  print("\t"*current_index, "current_index:", current_index, end="")
  if current_index<len(num):
    print(", num[", current_index, "]: ", num[current_index], sep="")
  else:
    print(", end of input")
  print("\t"*current_index, "required sum:", sum)
  # print_sets(current_index,num)
  # base checks
  if sum == 0:
    print("\t"*current_index, "** Subset with required sum exists:", candidate_set[2:], "**")
    return 1
  n = len(num)
  if n == 0 or current_index >= n:
    print("\t"*current_index, " Sum of subset {", candidate_set[2:], "} does not equal required sum (", required_sum ,"), backtracking to explore other branches", sep="")
    return 0
  # check if we have not already processed a similar problem
  if dp[current_index][sum] == -1:
    # recursive call while choosing the number at the current_index
    # if the number at current_index exceeds the remaining sum, we shouldn't proceed
    sum1 = 0
    if num[current_index] <= sum:
      sum1 = count_subsets_recursive(
        dp, num, sum - num[current_index], current_index + 1, candidate_set + ", " + str(num[current_index]))
      print("\t"*current_index, "sum1 at index", current_index, "is:", sum1)
      if sum1>0:
        print("\t"*current_index, " included num[", current_index, "]: ", num[current_index], sep="")
    # recursive call while excluding the number at the current_index
    sum2 = count_subsets_recursive(dp, num, sum, current_index + 1, candidate_set)
    print("\t"*current_index, "sum2 at index", current_index, "is:", sum2)
    if sum2>0:
      print("\t"*current_index, " excluded num[", current_index, "]: ", num[current_index], sep="")
    dp[current_index][sum] = sum1 + sum2
    print("\t"*current_index, " count of subsets at index ", current_index, " (sum1 + sum2: ", sum1, " + ", sum2, ") is: ", sum1+sum2, sep="")
    print_matrix(dp, current_index, num)
  else:
    print("\t"*current_index, "Already computed: dp[", current_index, "][", sum, "]: ", dp[current_index][sum], sep="")
  return dp[current_index][sum]
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, 1, 2, 3], 4],[[1, 2, 7, 1, 5], 9]]
  for arr in arrs:
    print("Finding total number of subsets with sum",arr[1],"in:",arr[0])
    result = count_subsets(arr[0], arr[1])
    print("Subsets with sum",arr[1],"are:",result)
    print("-"*100+"\n")
main()