Before starting up with the Equal Sum Partition Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Equal Sum Partition Problem. I’d also highly recommend you to go through the Subset Sum Problem since it’s the parent problem for Equal Sum Partition Problem.
With that being said, let’s get started.
Given a set of N non-negative integers, determine if the set can be partitioned into two subsets such that the sum of the elements in each of the two subsets is equal. …
Before starting up with the Subset Sum Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Subset Sum problem. I’d also recommend to go through the Knapsack Problem since it’s the parent problem for Subset Sum Problem.
With that being said, let’s begin!
Given a set of N non-negative integers and a target sum S, determine if there exists a subset of the given set such that the sum of the elements of the subset equals to S. …
Before starting up with the Knapsack Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Knapsack problem.
With that being said let’s begin !
The problem of 0–1 Knapsack goes something like this.
We are given an empty bag that can hold maximum of W weight. We have a set of N items. Each item has an associated value v and an associated weight w. …
In simple words one can say that it is an optimisation over plain recursion technique. This is achieved by reducing the number of recursive calls, either by storing the intermediate computed values or by deriving the final computation based on some kind of logical relation. This ultimately leads to reduced time complexities, thereby improving the overall performance of the solution.
Since it’s a programming paradigm thus it has nothing to do with being specific to a particular language or set of programming languages.
With that being said let’s dive into Dynamic Programming.
The key to understanding any problem’s solution that employs the use of Dynamic Programming (commonly referred to as DP), is Recursion. One must first master the skill to code up a recursive solution for the same problem. Building a DP based solution using either Tabulation or Memoization can then be very easily done with the help of the recursive code. …
Maps are nothing but a type of associative container which stores elements in the form of key-value pairs. For those of you who are familiar with python, you can think of maps like a dictionary in python.
A key in map is used to uniquely identify the element and the value contains the corresponding stored data. Thus a key has to be unique and cannot repeat but the values can be same for two different keys.
Enrolment Number : Name
Here Enrolment Number is the key and Name is the corresponding value. The data type of the key and value may or may not be the same. …
The Standard Template Library (STL) is a very useful set of template classes containing various containers. One among these containers is Lists. Today we’ll be having a look at Lists in STL. But before we proceed further I’d like to say that if this is your first time learning STL then I’d recommend you have a look at this article before beginning with this one.
With that being said let’s dive further into the topic by knowing what are lists in STL ?
Lists are a type of sequence containers which provides us with constant insertion and deletion time anywhere within the sequence given that we have obtained the corresponding iterator to the same. …
Iterators are something which is used to point at the memory addresses of STL containers’ elements. Thus providing a means to access the data stored within the container and ability to modify them. They can be simply thought of as pointers.
We need iterators in order to manipulate the containers. Containers on their own cannot be modified unless we make use of an iterator or a member function. The purpose is to isolate the user from the internal structure of the container thus helping with abstraction.
They provide a bridging or a connection between the algorithms and containers by allowing the algorithms to operate on the containers via them. …
The Standard Template Library (STL) in C++ is nothing but a set of template classes which provides us with the widely used data structures such as lists, stacks, maps, etc. along with iterators, functions and algorithms in order to play around with the data elements.
Containers are nothing but holder objects which stores other objects i.e. it’s elements. A container does the memory management for its elements and provides us with member functions or iterators in order to interact with it’s data elements.
Algorithms, defined under the header <algorithm>, are nothing but a collection of several functions which are designed in order to used on any sequence of elements that can be accessed using iterators or pointers. One thing to note about algorithms is that they do not change the way a data structure is organised in any way. …