Recursion not working as expected for target sum problem

Question

I wrote two different recursive functions in python to solve the following problem. The second function I wrote works correctly and returns the correct result; but the first function I wrote returns a wrong result. The only difference between the two functions is the base condition. Could you please explain to me why the first function returns a wrong result?

Problem statement:

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

My code:

# first function: returns the wrong result
def targetsum(nums, crnt, target):
  print(nums,crnt)
  if target==crnt:
    return 1
  if len(nums)==0:
    return 0
  result = (
    targetsum(nums[1:], crnt + nums[0], target)
    + targetsum(nums[1:], crnt - nums[0], target)
  )
  return result

# second function: returns the correct result
def dfs(curr, nums, target):
  print(nums,curr)
  if not nums:
    return (1 if curr == target else 0)         
  res = (
    dfs(curr + nums[0], nums[1:], target)
    + dfs(curr - nums[0], nums[1:], target)
  )
  return res

nums = [1,1,1,1,1] 
target = 3
crnt=0

print(targetsum(nums, crnt, target))   # prints 4

print(dfs(crnt, nums, target))         # prints 5

I expected the output 5, because there are 5 ways to assign symbols to make the sum of nums be target 3:

    -1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3

The second function, dfs, returns 5 as expected. But the first function, targetsum, returns 4 which is wrong. Why?

Answer 1

The base-case for the recursion is wrong in your first function targetsum. Function targetsum returns 1 immediately if crnt == target, even if we haven't reached the end of the array. But this is wrong: you should not return a result until you've reached the end of the array.

On your example with nums=[1,1,1,1,1] and target=3, the first recursive calls will go like this:

 1 1 1 1 1   crnt=0
+1 1 1 1 1   crnt=1
+1+1 1 1 1   crnt=2
+1+1+1 1 1   crnt=3
crnt==3==target!! return 1 immediately!!

Can you see the error in logic here? crnt is equal to target, yes, but we forgot to take into account the last two numbers in the array. We shouldn't return 1 immediately; in fact, there are not 1 but 2 possibilities to make target 3 with the beginning +1+1+1: the two possibilities are +1+1+1+1-1 and +1+1+1-1+1. But the only way to figure that out is to go deeper in the recursion. We haven't hit a base-case yet.

Your second function dfs handles the base case correctly: the conditional if not nums: means "if nums is empty:".