Decomposing a number as a sum of two products using tree recursion

Question

Below is the problem taken from page6 here.

The TAs want to print handouts for their students. However, for some unfathomable reason, both the printers are broken; the first printer only prints multiples of n1, and the second printer only prints multiples of n2. Help the TAs figure out whether or not it is possible to print an exact number of handouts! First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

def has_sum(sum, n1, n2):
"""
>>> has_sum(1, 3, 5)
False
>>> has_sum(5, 3, 5) # 1(5) + 0(3) = 5
True
>>> has_sum(11, 3, 5) # 2(3) + 1(5) = 11
True
"""

Solution

I think there is no mathematical solution except bruteforce recursion.

def f(sum, n1, n2):
 """
 >>> f(1, 3, 5)
 False
 >>> f(5, 3, 5) # 1(5) + 0(3) = 5
 True
 >>> f(11, 3, 5) # 2(3) + 1(5) = 11
 True
 >>> f(189, 4, 9)
 True
 """
 memoiz = []
 value = [] 
 def has_sum(sum, n1, n2, x=0, y=0):
 if x == 0 and y == 0:
 value.append(n1)
 value.append(n2) #execute once to reuse tup
 if (n1 + n2) == sum:
 return True
 if (memoiz) and ((n1 + n2) > sum): # inefficient base case, need to improve using math
 return False
 result1 = False
 result2 = False
 if (x+1, y) not in memoiz:
 memoiz.append((x+1, y)) #memoiz
 result1 = has_sum(sum, (x+1)*value[0], y*value[1], x+1, y)
 if (x, y+1) not in memoiz:
 memoiz.append((x, y+1)) #memoiz
 result2 = has_sum(sum, x*value[0], (y+1)*value[1], x, y+1)
 return result1 or result2
 return has_sum(sum, n1, n2)

Can we improve the base case that returns False?

• jonrsharpe: Why are you memoizing using a list?! in is O(n) and I've already shown you how to do it with a decorator.
• 200_success: See Linear Diophantine equations, two variables
• overexchange: Teacher did not teach decorator concept. I will go thru you question. I need to go thru some homework on decorators before using it.
• overexchange: @200_success yes, I got the same suggestion here
• 200_success: @jonrsharpe's has already mentioned in a previous answer to one of your questions that the most elegant way to memoize functions is to use a decorator. We don't mind reviewing your code, but it would be more rewarding if we can see that you are learning from our answers. (You may have noticed that your recent questions have not scored as well as your first few questions.)

Answer 1

First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

You haven't included an implementation without a helper function. You implemented memoization, which was not part of the description. In any case, memoization won't be possible without a helper function or annotations.

Code review

There are several problems with your implementation:

• memoiz shouldn't be a list, but a set
• The value variable is confusing: it merely stores the original values of n1 and n2, you could simply save those values before calling the helper function
• sum is a poor name for a variable, because it shadows the built-in named "sum"
• There should be spaces around operators to improve readability, for example instead of (x+1)*value[0] it should be (x + 1) * value[0]
• Instead of multiplying value[0] and value[1], it would be better to accumulate a sum
• If result1 is True, there's no need to evaluate result2

With the above tips, the solution can be simplified a bit and become more efficient:

memoiz = set()
def has_sum(sum, n1, n2, x=0, y=0):
 if n1 + n2 == sum:
 return True
 if n1 + n2 > sum:
 return False
 if (x+1, y) not in memoiz:
 memoiz.add((x+1, y))
 result1 = has_sum(sum, n1 + orig_n1, n2, x+1, y)
 if result1:
 return True
 if (x, y+1) not in memoiz:
 memoiz.add((x, y+1))
 return has_sum(sum, n1, n2 + orig_n2, x, y+1)
 return False
orig_n1, orig_n2 = n1, n2
return has_sum(sum, 0, 0)

An alternative solution

Consider this alternative algorithm:

• If target is 0, then we can reach it by 0 times n1 and n2
• If target is below 0, then we cannot reach it
• If target can be reached by a sum of multiples of n1 and n2, then target - n1 or target - n2 must be reachable too

Implementation using memoization:

memoize = { 0: True }
def helper(target):
 if target not in memoize:
 if target < 0:
 memoize[target] = False
 else:
 memoize[target] = helper(target - n1) or helper(target - n2)
 return memoize[target]
return helper(target)

Iterative solution

At first I overlooked your requirement of a recursive solution. For the record, this was my original suggestion using iterative logic.

---

Unless I'm missing something, you can solve this using a much simpler algorithm:

• If a solution exists, then sum == n1 * A + n2 * B where A and B are integers
• Loop from A = 0 to sum, by steps of n1
• If sum - A is divisible by n2, then a solution exists
• If the end of the loop is reached, then a solution doesn't exist

That is:

for A in range(0, sum + 1, n1):
 if (sum - A) % n2 == 0:
 return True
return False

• overexchange: This question is part of recursion lab
• janos: My bad, I overlooked your title. I rewrote my answer.
• overexchange: you said dict but you are using set(). what is the problem with list?
• janos: Changed the text to set to match the revised implementation. The problem with a list is that x in somelist is an \$O(n)\$ operation, while x in someset is an \$O(1)\$ operation
• overexchange: OK. how set is efficient from list in finding an element? What is the underlying implementation of set that it is efficient than list?