Skip to content
Advertisement

Recursion ( kind of sub-set sum, but not exactly ) – True if can buy pens at exact price, else False

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

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement