Recursively Finding out if a list of numbers can add up to a certain value

[sharyfomar]

Hello,
I have been following the algorithm lectures dealing with recursion on Freecodecamps’ youtube page delivered by Alvin. One of the examples involved finding out if a given set of numbers , say [1,4,5,2] could add up to 10.

def cansum(target,values):
    if target==0:
        return True
    if target<0:
        return False
    for i in values:
        rem=target-i
        
        if cansum(rem,values)==True:
            return True
        if cansum(rem,values)==False:
            return False
        
cansum(1,[2,1])

The function should theoretically give similar answers if we test
cansum(1,[1,2]) but in my case its not. If someone could point out what is wrong .
Thanks

[manjupillai16]

Hi @sharyfomar ,

I think this line is the problem:

rem=target-i

You could print the values of rem inside the for loop to understand.

[sharyfomar]

[edited explanation] Hey, Thanks

the remainder here is supposed to check for us if our number eventually reaches the base case[0 which gives True].
For example:
cansum(3,[1,4]) will evaluate as:
first iteration 3-1=2 not yet zero so we will continue
second iteration 2-4=-2 which according to our base case returns false.

if we try (1,[1,2]) we have rem=1-1=0 as our first iteration, which returns True,

the second iteration will be 1-2=-1 which according to our conditions will be False.

I found my error to be due to indentation at the last code

{if cansum(rem,values)==False:
return False} I have shifted it and its now in line with the for statement. Its working though I cant explain why

[manjupillai16]

I think I understand what you are trying to do but not what you explained above.
I feel that the target value is not changing in every loop.

target = target - i ← Try this instead of rem = target -i

and just assign rem = target before you call the recursive function.

I think it should fix the problem else I’ve misunderstood the question itself.

[ArielLeslie]

I’ve edited your post for readability. When you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read.

You can also use the “preformatted text” tool in the editor (</>) to add backticks around text.

See this post to find the backtick on your keyboard.
Note: Backticks (`) are not single quotes (’).

[manjupillai16]

Hey @sharyfomar ,

Now I understand why on printing out rem in your code, prints only 1-2!
It’s because of the ‘if statement’ inside the for loop, it issues a return statement which comes out of the cansum() function.

if cansum(rem,values)==False:
            return False

I was assuming the if statements to be outside the for loop, noticed it now when your code was indented.

target = target - i ← this should work - as mentioned above

[sharyfomar]

Thank you Bro, It has started to give correct answers