Adding two sum with recursion

November 11, 2021

Question: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.Each input would have exactly one solution, and you may not use the same element twice. for example.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

I’m trying one make a helper function that add the first number with each of the rest number, and run this helper function recursively on the give list nums. I’m not sure where my codes is wrong. (I know there are other more efficient algorithms, for the purpose of exercise pls stick to this approach)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # One function that takes a list, and find out first + i ==target, if exists
        def help_(lst,tar):
            for i, n in enumerate(lst[1:],start=1):
                if lst[0]+n ==tar:
                    return i
                else:
                    return False
                
        ctn=0
        #base case, if a sublist whose first num + another another is target
        if help_(nums,target) != False:
            return [0+ctn,help_(nums,target)+ctn] # return two indices from helper, adding the time it looped
        else: 
            ctn =+1
            return help_(nums[1:],target)

>Solution :

There are a few issues:

Your recursive call return help_(nums[1:],target) will not return a pair, but one index (or False), so this should never be returned in the main function. Instead make the recursive call on twoSum, which will return a pair (if successful). Then you will still need to add 1 to both indices before returning that.
The helper function is returning always in the first iteration of the loop. You should move the return False out of the loop’s body.
It is a pity that you call the helper function twice with the same arguments. Just store the result in a temporary variable to avoid re-executing it

Here is your code with those corrections:

class Solution:
    def twoSum(self, nums, target):
        
        # One function that takes a list, and find out first + i ==target, if exists
        def help_(lst,tar):
            for i, n in enumerate(lst[1:],start=1):
                if lst[0]+n ==tar:
                    return i
            return False
                
        ctn=0
        res = help_(nums,target)
        if res != False:
            return [0+ctn, res+ctn]
        else: 
            ctn =+1
            x, y = self.twoSum(nums[1:], target)
            return x+1, y+1

As you noted in your question this is not the most efficient way to solve this problem.

Using a dictionary leads to a better time complexity. In case you cannot find it, here is such a solution (spoiler):