Recursion Algorithms

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.

List of Algorithms


  1. Arrange balls

    There are p, q and r balls. arrange balls in a straight line such that no two balls of the same type are adjacent.

  2. Find Binomial coefficient

    A binomial coefficient, n choose k formula, is also known as combinations formula, and is defined as

  3. Find Nth Catalan Number

    Find Nth Catalan Number

  4. Climbing stairs with 3 moves

    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.

  5. Climbing stairs

    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.

  6. 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.

  7. 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.

  8. Find all subsequence combinations of a string

    Given a string 'abc', find all distinct subsequence combinations of it.

  9. Count number of derangements

    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].

  10. 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.

  11. Find Nth Fibonacci number

    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.

  12. House robber

    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.

  13. 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.

  14. 0/1 Knapsack problem

    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.

  15. Unbounded knapsack

    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.

  16. 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.

  17. Find longest common subsequence (LCS)

    Given two strings, s1 and s2, find length of the longest common subsequence. Return 0 for nothing common.

  18. Find longest common substring

    Given two strings 's1' and 's2', find the length of the longest common substring.

  19. 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.

  20. 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'.

  21. 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.

  22. Min cost path

    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.

  23. Minimum insertions to form a palindrome

    Given string str, find the minimum number of characters to be inserted to make it a palindrome.

  24. 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.

  25. 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.

  26. 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.

  27. 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.

  28. 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.

  29. Pascal's Triangle

    Given an integer n, find the first n rows of Pascal's triangle.

  30. 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**.

  31. 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.

  32. 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.

  33. Stacking box

    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.

  34. Subsequence with difference of 1

    Given a list of numbers, find the longest subsequence such that the absolute difference between adjacent elements is 1.

  35. Subset sum

    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.

  36. Maximize total tips

    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.

  37. Find Nth Tribonacci number

    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.

  38. 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.

  39. 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.

  40. Word Break

    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.