Recursive algorithms stand out due to their elegance in expressing solutions to problems that can be naturally divided into smaller, self-similar subproblems. This approach aligns perfectly with the core principle of "divide and conquer," a fundamental strategy in algorithm design.
Key Applications:
The primary focus when learning recursion should be on understanding how to break down a complex problem into smaller, more manageable subproblems. This emphasis on decomposition is crucial for developing a strong foundation in algorithmic thinking.
To emphasize the decomposition process, we often pass reduced lists to recursive calls instead of updating indices. This clearly illustrates how the problem size diminishes with each recursive step. For example, in a recursive function to find the factorial of a number, we pass n-1 to the next recursive call, effectively reducing the problem size.
While recursive solutions can be elegant, they may suffer from redundant calculations, leading to inefficient performance. Dynamic programming techniques can optimize recursive solutions by memoizing or tabulating results, avoiding repeated computations. However, understanding the core recursive approach and the decomposition process is fundamental before delving into optimization techniques.
There are p, q and r balls. arrange balls in a straight line such that no two balls of the same type are adjacent.
A binomial coefficient, n choose k formula, is also known as combinations formula, and is defined as
Find Nth Catalan Number
There are n stairs, and a person standing at the bottom can climb either 1 stair, 2 stairs or 3 staris at a time, count the number of ways that a person can reach at the top.
There are n stairs, and a person standing at the bottom can climb either 1 stair or 2 stairs at a time, count the number of ways that a person can reach at the top.
Find minimum coins to make change
Given a list of coins[] of different denominations with infinite supply of each of the coins. Find the minimum number of coins required to make the given sum. If it's not possible to make a change, return -1.
Find number of way to make coin change
Given a list of coins[] representing different denominations, count all combinations of the coins to make a given value sum.
Find all subsequence combinations of a string
Given a string 'abc', find all distinct subsequence combinations of it.
Given a number n, find number of derangements in a set of n elements. A Derangement is a permutation with no element appears in its original position. For example, a derangement of [0, 1, 2] is [2, 0, 1].
Find all distinct subset sums of an array
Given a list of numbers, find all distinct sums that can be generated from the subsets of the given list and return them in increasing order.
Given a positive integer n, find the nth Fibonacci number. Fibonacci numbers, when it starts from 0, are calculaed as F(n), where F(1) = 0, F(2) = 1, and F(n) = F(n-1) + F(n-2) for n > 2. Example of first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
A robber wants to steal money from n houses built in a line, each of which contains some money in it. Given he can’t steal from two adjacent houses, find the maximum amount of money can be steal.
Find minimum of jumps to reach end
Imagine you're hopping along a number line. Each number on the line represents a position in a list of numbers. Each number on the line tells you the maximum distance you can hop forward from that position. Find the fewest hops needed to reach the very end of the number line, starting from the beginning. If a number is zero, you can't hop from that position at all.
Given list of N items where each item has some [weight, value] associated with it, put the items into a knapsack of capacity W to maximize the sum of values associated with the items. Break item is not allowed.
Given list of N items where each item has some [weight, value] associated with it, put the items into a knapsack of capacity W to maximize the sum of values associated with the items. Repetition of items is allowed.
Longest common increasing subsequence (LCS + LIS)
Given two arrays, a[] and b[], find the length of the longest common increasing subsequence(LCIS). LCIS refers to a subsequence that is present in both arrays and strictly increases.
Find longest common subsequence (LCS)
Given two strings, s1 and s2, find length of the longest common subsequence. Return 0 for nothing common.
Given two strings 's1' and 's2', find the length of the longest common substring.
Find longest increasing subsequence (LIS)
Given an array of size n, find the length of the longest increasing subsequence (LIS), in which the elements of the subsequence are sorted in increasing order.
Longest palindromic subsequence (LPS)
Given a string, find the length of the longest palindromic subsequence in it. For example, the length of the longest palindromic subsequence for 'bbbab' is 4 and the sequence is 'bbbb'.
Maximum size of square sub-matrix with all 1s
Given a binary matrix of size n * m, find out the maximum size of square sub-matrix with all 1s.
Given a 2d matrix cost[][], calculate the minimum cost path from (0, 0) to (m, n). Only move down, right and diagonally lower cells from a given cell is allowed.
Minimum insertions to form a palindrome
Given string str, find the minimum number of characters to be inserted to make it a palindrome.
Find the minimum number of edits
Given two strings s1 and s2 of lengths m and n, find the minimum number of edits (operations) to convert "s1" into "s2" using operations of insert, remove or replace of a char.
Number of unique BST with N keys
Given an integer n, count the total number of unique BSTs that can be made using values from 1 to n.
Maximize number segments of cutted in length x, y and z
Given a rod of length n, maximize the total number of segments can be cutted in length of x, y, and z.
Find number of ways paint a fence with n posts and k colors
Find out the number of ways of painting a fence with n posts and k colors so that not more than two consecutive posts have the same color.
Partition a set into two subsets of equal sum
Given a list of numbers, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
Given an integer n, find the first n rows of Pascal's triangle.
Regular expression wildcard pattern matching
Given a text and a pattern, test if pattern matches text. Both text and pattern consist of only lowercase alphabets while pattern also consists special characters of "." and "\*". "." matches any single character and **"\*" matches zero or more of the preceding character**.
Find number of permutation with K inversions
Given two numbers n and k, find how many permutations of the first n number have exactly k inversion. An inversion is defined as a[i] > a[j] for i < j.
Print maximum number of A’s using given four keys
Give a special keyboard with the following four keys Key 1: Prints 'A' on screen, Key 2: Select screen, Key 3: Copy selection, Key 4: Paste selection on screen after what has already been printed. Given a number N times (with the above four keys), write a program to produce maximum numbers of A's.
Given a list of three values, height, width and length, create a stack of boxes that is as tall as possible. A box can be stacked on top of another box if dimensions of its 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. A box can stack in any orientation and multiple instances of the same type of box is allowed.
Subsequence with difference of 1
Given a list of numbers, find the longest subsequence such that the absolute difference between adjacent elements is 1.
Given a list[] of non-negative integers and a value sum, check if there is a subset of the given list whose sum is equal to the given number.
A restaurant received n orders. The two waiters A and B in the restaurant change different amount of tip, listed in A[] and B[], for an order. Given A can handle max X order and B can handle max Y order, Find out the maximum possible amount of total tips to handle all the orders.
Given a positive integer n, find the nth Tribonacci number. Tribonacci numbers, when it starts from 0, are calculaed as T(n), where T(1) = T(2) = 0, T(3) = 1, and T(n) = T(n-1) + T(n-2) + T(n-3) for n > 3. Example of first few Tribonacci numbers are 0, 0, 1, 1, 2, 4, 7, 13, 24, 44.
Count unique paths in matrix from top left to bottom right
Given m x n matrix, count of all unique possible paths from top left to the bottom right. From each cell, only move right or down is allowed.
Weighted interval job scheduling
Given n jobs where every job has the start time, finish time and profit associated. Find the maximum profit in scheduling jobs such that no two jobs overlap.
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.