recursion

Solving 0/1 Knapsack problem using Recursion

Introduction A knapsack is a bag with straps, usually carried by soldiers to help them take their valuables or things which they might need during their journey. The 0/1 knapsack problem is a very famous interview problem. The problem statement is as follows: Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried in a knapsack of capacity W (where W is the weight). It is required that the cumulative value of the items in the knapsack is maximum value possible. In simple words, it asks you to pick certain items from the...
Read More

Solving Sudoku using Backtracking

Introduction This post is the continuation of the backtracking series. Sudoku can be solved using multiple algorithms based on Neural Networks and Genetic Algorithms by doing exhaustive searches in the solution space. However, here we are focusing on solving Sudoku using backtracking algorithm. For people who are unaware of the Sudoku puzzle, please check out Wikipedia for details. For a brief description read below: A Sudoku puzzle is a 9 * 9 grid. Few cells in the grid contain random numbers between 1 and 9 (both inclusive) A fully solved Sudoku must contain numbers through 1-...
Read More

Print all paths of robot through the grid

Introduction This is a supplement to the previous post where we were interested in just one path of a robot from top left corner to the bottom right corner. In this post we will print all paths of robot moving through a given grid containing few blocked cells. The algorithm for this solution remains the same, we just need few tricks to get that right. Here, I will explain the idea behind printing all paths of robot through the grid. Approach Here, let us discuss what different we need to do to print all the paths. As we can recall from the previous post, the moment we reached the destina...
Read More

Find Path through grid – constrained motion

Introduction This is another addition to the backtracking series of problems. The problem is asked in many interviews in many different forms. Here are few of them: Given a grid where few of the cells are blocked. You have a robot placed at the top left corner of the grid. Find path through grid such that the robot starts from the top left corner and moves to the bottom right corner. Another form just asks for all possible paths from one cell to another into a grid. Of course there are constraints on the movement of the robot, else you would end up going in circles and the paths wo...
Read More

Solution to find Interleaving of Strings

Introduction This post is an enhancement over one of the previous posts where the task was to find if a given string C is an interleaving of strings A and B. To know more about the problem description, please visit the previous post Solution The previous solution is a iterative solution which requires lot of space. Here we will discuss a recursive solution. Hopefully with small code foot print. Before we jump into the code, let us understand the idea behind the solution. Here are the example Strings A, B and C A -> abcd B -> ade C -> abadcde The recursive algorithm...
Read More

Paint Fill Implementation – Image Editing

Introduction Most of the image editing software like Microsoft paint, Paint.NET, Adobe Photoshop offer features like paint fill. This post is an attempt to define a simple version of the algorithm which is used to implement paint fill. The problem definition goes like this: There is a grid with dimensions N*M such that each cell of the grid is colored. The paint fill technique allows a user to choose a color to be filled, say K and a cell C(i,j). If the cell C(i,j) has the same color as K, then do nothing. If the cell C(i,j) has a color L which is different from K then find all the...
Read More

Data Structures and Algorithms – Recursion

Introduction The article Data Structures and Algorithms – Recursion is the third in series, of online course for Data Structure Algorithm. This is an effort to introduce and explain the Recursion methodology of algorithm design and programming. We will try to write some recursion based code and analyze the complexity of the algorithms in detail. Recursion It is the concept of defining a method that makes a call to itself and the call is termed as a recursive call. This is a readable and still efficient way of designing algorithms in the scenario where the problem in hand can be redefined by...
Read More