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

Basics of C++ | C++ Tutorial

This is our first tutorial on C++. and there are a lot of features in C++. but we will focus on those part which is beneficial for competitive programming. and after learning new concept we will solve some questions related to those concepts, so that we can use these concepts to solve bigger problems. First of all let's get some theoritical knowledge about C++: 1.C++ is an Object Oriented Programming language(we will explain this point later). 2.It is developed by Bjarne Stroustrup in 1979. 3.C++ is high level language.     What is High level language?      ->they are those language which is machine independent, that means we can compile or run it on any machine.     ->Easy to debug and maintain.     ->Portable. so if any language has these features then we can consider it as a High level language.       eg:C++, Java etc.. 4.C++ provides data security. 5.Main features of C++ is Polymorphism, I...
Post a Comment
Read more

Array vs Linked List

Benefits of Linked List over Array: 1.Deletion and Insertion:  -> Deletion and Insertion in linked is less time consuming over array.    Deletion: if we delete any element from array except last element, then we have to shift all element backward       after the deleted element. so suppose we have an array of 10 integers and if we delete element from index five, then we have to shift element from index 6 to 9 backward. and it will consume more time. while deletion in list is less time consuming. we will see it later. Insertion: if we insert an element in the array except last index, then  we have to shift the remaining element after that index towards right. and it will take more time. while insertion in linked list is much profitable than array. 2.We can dynamically increase the size of the linked list as we allocate memory to nodes at runtime(or dynamically). while in case of array we have to declare it size during writing of code. ...
Post a Comment
Read more

Symmetric Tree | Interview Problem

Introduction: In this tutorial we are going to solve a good question which will clear your doubts on how BFS or level order traversal is useful to solve binary tree problems. this is basically a question from Leetcode, and it is really very good problem to practice BFS. Problem Statement: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: But the following [1,2,2,null,3,null,3] is not: Link : Leetcode Link please make binary tree on paper by the given array above. and you will get a clear picture of the problem. what we are going to do in this problem. Solution: As we know we are going to apply BFS to solve this problem. actually you have to just get one thing to solve this problem. we will perform BFS, but with little change or modification. So first we will store the root->val in a vector or array of the left subtree. and during this we will first insert left child and then ...
Post a Comment
Read more