How to solve two sum problem using recursion?-CodePudding

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] .

So instead of the bruteforce method I was trying to solve this problem using recursion.It worked fine for a few test cases but it failed the test case when nums is [3,2,3] and target =6,it returns a empty array in this case. Its running into an infinite loop. How do I rectify this error?

Below is my code

class Solution {

public:
    void giveSolution(vector<int>& nums,int i,int target, vector<int> &v){
       
        if(nums.size()==0){
            return;
        }
        if(i==nums.size()){
            return;
        }
        if(nums[i] nums[i 1]==target){
            v.push_back(i);
            v.push_back((i 1));
        }
        else{
            giveSolution(nums,i 1,target,v);
        }
        
        
    }

    vector<int> twoSum(vector<int>& nums, int target) {
         vector<int> v;
     giveSolution(nums,0,target,v);
        return v;
      
      }
};

CodePudding user response：

The check

    if(i==nums.size()){
        return;
    }

is too late. Because already when i == nums.size()-1 you access the vector out-of-bounds in the next line:

 if(nums[i] nums[i 1]==target){
              // ^^ i 1 == nums.size()

This is undefined and the output of the program could be anything. Use at rather than [] to get a runtime error instead of undefined behavior.

Moreover, you are only considering adjacent elements of the input, while the tasks asks you to find any two numbers.

CodePudding user response：

Your implementation assumes that the two values must be found at adjacent indices in the vector.

Your code needs to consider the possibility that those two values are further apart. You can go for the brute-force idea to search for the second value in the remainder of the vector. So then your recursive function would become:

    void giveSolution(vector<int>& nums,int i,int target, vector<int> &v){
        if (i >= nums.size() - 1) { // Exit one step earlier as there is no more PAIR
            return;
        }
        // Find where the counter part of the current value is:
        auto it = find(nums.begin()   i   1, nums.end(), target - nums[i]);
        if (it != nums.end()) { // Found it!
            v.push_back(i);
            v.push_back(it - nums.begin()); // ...at this index
        }
        else{
            giveSolution(nums, i 1, target, v);
        }
    }

Although recursion can at times be a very interesting option, it isn't here. This doesn't improve on the iterative brute force way to do it. It performs even worse, as it needs extra memory for the call stack, and for larger inputs it could run out of stack memory.

An efficient solution will make use of a hash map -- no recursion.

CodePudding user response：

What about a simple loop (sliding window approach) rather than a recursive algorithm?

Here' s my code:

class Solution {

    public:

        vector<int> giveSolution(vector<int>& nums, int target){

           vector<int> v;

           for(int i = 0; i < nums.size() - 1; i  ){

               if(nums.at(i)   nums.at(i   1) == target){

                   v.push_back(i);
                   v.push_back(i   1);

               }

           }

           return v;

       }

};