I have this question: you have a list of [7,9,11] pens. you have a function:
def can_i_buy(x):
you need to check whether or not if you can buy the exact amount.
for example, I have X=23
I can buy 1*9, 2*7
I just need to return True if it is able, false else.
I saw the answer, they did it brute force with 3 for loops ( crazy ).
I tried recursion, it is good, but seems like it is long + duplicated parts + its not exactly good, cus I don’t know where to put the False statement.. what is my exit point.
The code works, but not exactly.
def can_i_buy(x): # 23 return helper(x, [7,9,11]) def helper(x, lst): if x == 0: return True if x < 0: return take_1 = helper(x - lst[0], lst) if take_1 == True: return take_1 take_2 = helper(x - lst[1], lst) if take_2 == True: return take_2 take_3 = helper(x - lst[2], lst) if take_3 == True: return take_3
How to fix it? also, what is my thought on the exit statement here? I dont know how to exit it… Where should I put false, and how?
Edit: added prints + outputs
print(can_i_buy(24)) print(can_i_buy(23)) print(can_i_buy(7)) print(can_i_buy(14))
output:
None True True True
I should receive at none – False. but I dont know where to put the False statement… when all the recursion end, I dont know how to put it.
Advertisement
Answer
The recursive call should be made with each price subtracted from x
, until x
is either 0 (in which case return True
) or less than 0 (in which case return False
):
def can_i_buy(x, lst): return not x or x > 0 and any(can_i_buy(x - i, lst) for i in lst)
If you just want your code fixed, you can return False
at the end of the function when all conditions that would return True
fall through:
def helper(x, lst): if x == 0: return True if x > 0: take_1 = helper(x - lst[0], lst) if take_1 == True: return take_1 take_2 = helper(x - lst[1], lst) if take_2 == True: return take_2 take_3 = helper(x - lst[2], lst) if take_3 == True: return take_3 return False
Or if you are allowed to make a for
loop:
def helper(x, lst): if x == 0: return True if x > 0: for i in lst: if helper(x - i, lst): return True return False
Demo: https://replit.com/@blhsing/MortifiedImmediateCheckpoint