Skip to main content

Target Sum | Backtracking Problem

Introduction:
In this tutorial we are going to solve a problem "Target Sum" which is from leetcode. and believe me it's really a good problem to understand Backtracking(Recursion). and if you try to understand the problem as well as code you will get a clear picture of Backtracking.


Problem Statement: Link To Problem
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Solution:

As given in question, we have two operation + and -. so we will make recursive 
call for + and - . and if we have sum as target and we have reached upto the last
index then we will increase count.




Full Code:

 int count=0;
    void helper(vector<int>& nums, int i, int ans, int s){
        if(ans==s && i==nums.size()){
            count++;
        }
        if(i==nums.size())
            return ;
        
          helper(nums,i+1,ans+nums[i],s);
          helper(nums,i+1,ans-nums[i],s);
    }
    int findTargetSumWays(vector<int>& nums, int S) {
        if(nums.size()==0)
            return false;
        
         helper(nums,0,0,S);
        return count;

    }
Conclusion:
This is really a good problem to practice backtracking. and just do a dry run on paper and you will
get things in very clear way. if still have any query, then comment it down.

Comments

Post a Comment

Popular posts from this blog

Disjiont Set Union-Find Data Structure | Code In C++

 Introduction:  In this tutorial we are going to write full program of disjoint set union find advance data structure in c++.  Problem Description: Disjoint Set Union (DSU) is an advance data structure, which basically uses in graph algorithms to find cycles. Codes:  Method1: Brute Force #include<bits/stdc++.h> using namespace std; int find(int f,vector<int>&dsuf){     if(dsuf[f]==-1)         return f;     return find(dsuf[f],dsuf); } void union_op(int from, int to, vector<int>& dsuf){     dsuf[from]=to; } bool isCycle(vector<pair<int,int> >&edge_list, vector<int>&dsuf){     for(int i=0;i<edge_list.size();i++){         int parent1=find(edge_list[i].first,dsuf);         int parent2=find(edge_list[i].second,dsuf);         if(parent1==pare...
Post a Comment
Read more

Linked List Data Structure | Add Two Number Explanation

Introduction: In this tutorial, we are going to solve a very famous problem on Linked List. It is also an important question for coding interview. so let's see the problem and understand it in detail. Problem Statement: There are two numbers and each digit of number is represented by a node of linked list.and we have to add these two numbers, which is given in the form of linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 eg: num1 = 2354;       num2 = 875; see the image below: Solution: Now let's solve it. In this problem there may be three possibilities. First: Number of Nodes in the first linked list is greater than second linked list. Second: Number of Nodes in first linked list is less than second list. Third: Number of Nodes in the both linked list is equal. Here number of nodes means number of digits in both number. Another thing we have to keep in mind is that if we add two digits then there may be possibility of gen...
Post a Comment
Read more

Integrating Frontend to Backend | MERN stack(100% working)

How to Integrate frontend to backend in MERN stack? For integrating the frontend to backend just do two things. Step1: Go and install cors on both side (front end as well as backend)              To install cors simply open the folder into terminal and type npm install cors--save. step 2: just go to your front end section(react app) open package.json file.                 and just add one line into package.json file.           "proxy":"http://localhost:4000" here i am using 4000, so what is 4000 ?. this is the port  on which our backend is listening. so it may be possible that u may have other port number on which your server is listening. so put yours port number on which your backend server is listening. and this proxy thing we have to add in frontend part not in backend part. Now it may be possible that you want to know ...
Post a Comment
Read more