Snippets Collections
def count_partitions(n, m):
  if (n == 0 ): 
    return 1 # there is only 1 way i.e. to leave it unpartitioned
  if (m == 0 or n < 0):
    return 0 # there is no way to divide n into 0 partions or if n is -ve (latter one from edge case of recursion call of n - m)
  else:
    return count_partitions(n - m, m) + count_partitions(n, m - 1)

print(count_partitions(9, 5)) # 23
  
def uniquePaths(n, m):
  if (n == 1 or m == 1):
    return 1
  else:
    return uniquePaths(n - 1, m) + uniquePaths(n, m - 1)

print(uniquePaths(3, 3))
class Tree(object):
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right 
 
tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))


def find_paths(root, required_sum):
    allPaths = []
  
    def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
      if currentNode is None:
        return
    
      # add the current node to the path
      currentPath.append(currentNode.val)
    
      # if the current node is a leaf and its value is equal to required_sum, save the current path
      if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
        allPaths.append(list(currentPath))
      else:
        # traverse the left sub-tree
        find_paths_recursive(currentNode.left, required_sum -
                             currentNode.val, currentPath, allPaths)
        # traverse the right sub-tree
        find_paths_recursive(currentNode.right, required_sum -
                             currentNode.val, currentPath, allPaths)
    
      # remove the current node from the path to backtrack,
      # we need to remove the current node while we are going up the recursive call stack.
      del currentPath[-1]
    
    find_paths_recursive(root, required_sum, [], allPaths)
    
    return allPaths

find_paths(tx, 5)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        #order of first two conditionals is important 
        if not subRoot: return True 
        if not root: return False 
        if self.sameTree(root, subRoot): return True 
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
        
        
    def sameTree(self, s, t): 
        if not s and not t: return True 
        if s and t and s.val == t.val: 
            return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right) 

        return False 
        
        
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True 
        if not p or not q: return False 
        if p.val != q.val: return False 
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        
function deepCopy(obj){
    let toString = Object.prototype.toString;
    if(typeof obj !== 'object') return obj;
    if(obj === null) return null;
    if(Array.isArray(obj)) return obj.map(deepCopy);
    let newObj = {};
    for(let key in obj){
        if(toString.call(obj[key])==='[object Date]'){
            newObj[key] = new Date(obj[key])
        } else if(toString.call(obj[key])==='[object RegExp]'){
            newObj[key] = new RegExp(obj[key])
        }else{
            newObj[key] = deepCopy(obj[key]);
        }
    }
    return newObj;
}
function flatten(arr) {
  let flat = []
  
  for(let prop of arr){
    if(Array.isArray(prop)){
      flat.push(...flattan(prop))
    } else {
      flat.push(prop)
    }
  }
  return flat
}
function getSubstringCount(s) {
    // Write your code here
    let [current, prev, result] = [1, 0, 0]
    
    for(let i=1; i<s.length; i++){
        let left = s[i-1]
        let right = s[i]
        if(left == right){
            current++
        } else {
            prev = current
            current = 1
        }
        if(prev >= current){
            result++
        }
    }
    return result
}
//find fibonacci numbers

function fib(n){
  if(n >=3 ){
    return fib(n-1) + fib(n-2)
  } else {
    return 1;
  }
}

console.log(fib(10))
class Solution
{
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
    {
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        Collections.sort(res); 
        return res;
                    
    }
    
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
    {
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            baseRes.add(""); 
  
            //returning a list containing empty string.
            return baseRes; 
        } 
        
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
  
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
      
        String code = hash[ch - '0']; 
  
        for (String val : prevRes) { 
  
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
            } 
        } 
        //returning the list.
        return Res; 
    }
}
class LexSort
{
    static void solve(String s,String out, ArrayList<String> ans ,int i){
        if(i==s.length()){
            ans.add(out);
            return;
        }
        char ch=s.charAt(i);
        solve(s,out,ans,i+1);
        solve(s,out+String.valueOf(ch),ans,i+1);
    }
    
    //Function to return the lexicographically sorted power-set of the string.
    static ArrayList<String> powerSet(String s)
    {
        ArrayList<String> ans= new ArrayList<>();
        solve(s,"",ans,0);
        return ans;
    }
}
class Solution
{
    public long modfun(long n, long  R)
    {
        // Base cases 
        if (n == 0) 
            return 0; 
        // power zero mean answer is 1
        if (R == 0)  
            return 1; 
        // If R is even 
        long y; 
        if (R % 2 == 0) { 
            // finding r/2 power as power is even then storing answer in y and if power is even like 2^4 we can simply do (2^2)*(2^2)
            y = modfun(n, R/2);  
            y = (y * y) % 1000000007; 
        } 
      
        // If R is odd 
        else { 
            y = n % 1000000007; 
            // reduce the power by 1 to make it even. The reducing power by one can be done if we take one n out. Like 2^3 can be written as 2*(2^2)
            y = (y * modfun(n, R - 1) % 1000000007) % 1000000007; 
        } 
        // finally return the answer (y+mod)%mod = (y%mod+mod%mod)%mod = (y%mod)%mod
        return ((y + 1000000007) % 1000000007);  
        }
        
        
    long power(int N,int R)
    {
        return modfun(N,R)%1000000007;
        
    }

}
class Solution
{
    static int RecursivePower(int n, int p)
    {
       if(p==0){
           return 1;
       }
       return n*RecursivePower(n, p-1);
    }
}
class Solution
{
    public static boolean check(int n,int counter)
    {
        if(counter<=n){
            if(n%counter==0)
                return false;
		    // calculate next position of input number
		    n=n-n/counter;
		    counter++;
		    // make recursive call with updated counter 
		    // and position return check(n, counter);
		    return check(n, counter);
        }    
       	else
       		return true;
    }
    
    // n: Input n
    // Return True if the given number is a lucky number else return False
    public static boolean isLucky(int n)
    {
        return check(n,2);
    }
}
class Solution
{
    public static int digitalRoot(int n)
    {
        if(n < 10)
            return n;

        return digitalRoot(n%10 + n/10);
    }
}
class Solution
{
    public static int countDigits(int n)
    {
        if(n<10)
            return 1;
        else
            // recursively count the digits of n
            return 1+countDigits(n/10);
    }
}
public class Permutation
{
	public static void main(String[] args)
	{
		String str = "ABC";
		int n = str.length();
		Permutation permutation = new Permutation();
		permutation.permute(str, 0, n-1);
	}

	/**
	* permutation function
	* @param str string to calculate permutation for
	* @param l starting index
	* @param r end index
	*/
	private void permute(String str, int l, int r)
	{
		if (l == r)
			System.out.println(str);
		else
		{
			for (int i = l; i <= r; i++)
			{
				str = swap(str,l,i);
				permute(str, l+1, r);
				str = swap(str,l,i);
			}
		}
	}

	/**
	* Swap Characters at position
	* @param a string value
	* @param i position 1
	* @param j position 2
	* @return swapped string
	*/
	public String swap(String a, int i, int j)
	{
		char[] arr = a.toCharArray();
		char temp = arr[i] ;
		arr[i] = arr[j];
		arr[j] = temp;
		return String.valueOf(arr);
	}

}
// Naive recursive solution : Time Complexity : Θ(2^n)

import java.io.*;
import java.util.*;

class GFG {

	static int countSubsets(int arr[], int n, int sum)
	{
		if(n == 0)
			return sum==0 ? 1 : 0;

		return countSubsets(arr, n-1, sum) + countSubsets(arr, n-1, sum - arr[n-1]);
	}

	public static void main (String[] args) 
    {
		int n = 3, arr[]= {10, 20, 15}, sum = 25;

		System.out.println(countSubsets(arr, n, sum));
	}
}
// Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int check(int n, int k)
    {
    	if(n == 1)
    		return 0;
    	else
    		return (check(n - 1, k) + k) % n;
    }

    static int josephus(int n, int k)
    {
    	return check(n, k) + 1;
    }
      
    public static void main(String args[]) 
    { 
        System.out.println(josephus(5, 3));  
    } 
}
import java.util.*;
import java.io.*;

class GFG 
{ 
    static void ToH(int n, char A, char B, char C) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move 1 from " +  A + " to " + C); 
            return; 
        } 
        ToH(n-1, A, C, B); 
        System.out.println("Move " + n + " from " +  A + " to " + C); 
        ToH(n-1, B, A, C); 
    } 
   
    public static void main(String args[]) 
    { 
        int n = 2; 
        ToH(n, 'A', 'B', 'C');  
    } 
}
import java.io.*;
import java.util.*;

class GFG 
{
	static void printSub(String str, String curr, int index)
	{
		if(index == str.length())
		{
			System.out.print(curr+" ");
			return;
		}

		printSub(str, curr, index + 1);
		printSub(str, curr+str.charAt(index), index + 1);
	}
  
    public static void main(String [] args) 
    {
    	String str = "ABC";
    	
    	printSub(str, "", 0); 
    }
}
import java.io.*;
import java.util.*;

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}
// Sum of Digits Using Recursion : Time Complexity : O(d), Space Complexity : O(d) 
// where d is the number of digits in number

import java.io.*;
import java.util.*;

class GFG 
{
	static int fun(int n)
	{
		if(n < 10)
			return n;

		return fun(n / 10) + n % 10;
	}
    public static void main(String [] args) 
    {
    	System.out.println(fun(253));
    }
}


// Iterative : Time Complexity : O(d), Space Complexity : O(1) {No Overhead & Less Aux. Space}

	static int getSum(int n)
	{
		int sum = 0;

		while (n != 0) {
			sum = sum + n % 10;
			n = n / 10;
		}

		return sum;
	}
// Time Complexity : O(n), Space Complexity : O(n)

import java.io.*;
import java.util.*;

class GFG 
{
	static boolean isPalindrome(String str, int start, int end)
	{
		if(start >= end)
			return true;

		return ((str.charAt(start)==str.charAt(end)) && 
			     isPalindrome(str, start + 1, end - 1));
	}
    public static void main(String [] args) 
    {
    	String s = "GeekskeeG";

    	System.out.println(isPalindrome(s, 0, s.length() -1));
    }
}
// Time Complexity : O(n), Space Complexity : O(n)

import java.io.*;
import java.util.*;

class GFG 
{
	static int getSum(int n)
	{
		if(n == 0)
			return 0;

		return n + getSum(n - 1);
	}
    public static void main(String [] args) 
    {
    	int n = 4;
    	
    	System.out.println(getSum(n));
    }
}
// Time Complexity: O(2^n), Auxiliary Space: O(N).
// Fibonacci Series using Recursion

class fibonacci
{
	static int fib(int n)
	{
      // if (n == 0) return 0;
      // if (n == 1) return 1;
      if (n <= 1)
      	return n;
      
      return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
      int n = 9;
      System.out.println(fib(n));
	}
}
// NON-TAIL RECURSIVE
 
import java.io.*;
import java.util.*;
 
class GFG 
{

	static void fun(int n)
	{
		if(n == 0 || n == 1)
			return 1;
 
		return n*fact(n - 1);
 
	}
  
    public static void main(String [] args) 
    {
    	fun(3);
    }

}




// TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG {

	
	static int fact(int n, int k)
	{
		if(n == 0 || n == 1)
			return k;

		return fact(n - 1, k * n);

	}
  
    public static void main(String [] args) 
    {
    	System.out.println(fact(3, 1));
    }

}
// Example1 : NON-TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG 
{
  	// Print N to 1 Using Recursion
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.print(n+" ");

		fun(n - 1);

	}
    public static void main(String [] args) 
    {
    	fun(3);
    }
}

// Example2 : TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG 
{
  	// Print 1 to N Using Recursion
	static void fun(int n, int k)
	{
		if(n == 0)
			return;

		System.out.print(k+" ");

		fun(n - 1, k + 1);

	}
    public static void main(String [] args) 
    {
    	fun(3, 1);
    }
}
// Time Complexity : O(n), Space Complexity : O(n) (Recursive)

import java.io.*;
import java.util.*;

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		printToN(n - 1);

		System.out.print(n+" ");

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		System.out.print(n+" ");
		
		printToN(n - 1);

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;
		
		fun(n / 2);

		System.out.println(n % 2);

	}
    public static void main(String [] args) 
    {
        fun(7);
    }

}
class GFG {

	
	static int fun(int n)
	{
		if(n == 1)
			return 0;
		else
			return 1 + fun(n / 2);
	}
    public static void main(String [] args) 
    {
        System.out.println(fun(16));
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.println(n);

		fun(n - 1);

		System.out.println(n);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		fun(n - 1);

		System.out.println(n);
		
		fun(n - 1);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void fun1(int n)
	{
		if(n == 0)
			return;

		System.out.println("GFG");

		fun1(n - 1);
	}
    public static void main(String [] args) 
    {
        fun1(2);
    }

}
import java.io.*;
import java.util.*;

class GFG {

	
	static void fun1()
	{
		System.out.println("fun1");
	}

	static void fun2()
	{
		System.out.println("Before fun1");

		fun1();

		System.out.println("After fun1");
	}

	public static void main (String[] args) {
		
		System.out.println("Before fun2");

		fun2();

		System.out.println("After fun2");

	}
}
import java.util.*;

public class Main {

  public static void main(String[] args) {
    // Write your code here

    int[] arr = {1,2,7,4,5};

    boolean ans = sorted(arr, 0);

    System.out.print(ans);

  }

  public static boolean sorted(int[] arr,int index) {
    if(index == arr.length-1){
      return true;
    }

    return arr[index]<arr[index+1] && sorted(arr, index+1);

  }
}
star

Mon Dec 19 2022 20:37:00 GMT+0000 (Coordinated Universal Time)

#recursion #python
star

Mon Dec 19 2022 19:32:39 GMT+0000 (Coordinated Universal Time) https://youtu.be/ngCos392W4w

#recursion #python
star

Mon Jul 18 2022 22:17:42 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/same-tree/submissions/

#python #tree #recursion #dfs #neetcode
star

Sun Jun 19 2022 04:40:24 GMT+0000 (Coordinated Universal Time)

#javascript #object #deep #copy #clone #recursion
star

Sun Jun 05 2022 02:02:30 GMT+0000 (Coordinated Universal Time)

#javascript #fibonacci #recursion #algorithm
star

Thu May 26 2022 19:09:19 GMT+0000 (Coordinated Universal Time)

#javascript #fibonacci #recursion #algorithm
star

Mon May 23 2022 23:09:54 GMT+0000 (Coordinated Universal Time)

#javascript #fibonacci #recursion #algorithm
star

Sun Feb 06 2022 23:42:45 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/possible-words-from-phone-digits-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits
star

Sun Feb 06 2022 23:27:01 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-set-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #powerset
star

Sun Feb 06 2022 23:19:49 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-of-numbers-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #power #powerof numbers
star

Sun Feb 06 2022 23:13:54 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #powerusing recursion #power
star

Sun Feb 06 2022 23:08:00 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/lucky-numbers2911/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #luckynumbers
star

Sun Feb 06 2022 22:48:51 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/digital-root/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #digitalroot
star

Sun Feb 06 2022 22:43:14 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/count-total-digits-in-a-number/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #countdigits
star

Sun Feb 06 2022 22:26:48 GMT+0000 (Coordinated Universal Time) https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

#java #gfg #geeksforgeeks #lecture #recursion #stringpermutations
star

Sun Feb 06 2022 22:06:53 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/josephus-problem/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #josephusproblem
star

Sun Feb 06 2022 21:54:48 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/tower-of-hanoi-1587115621/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #towerofhanoi #toh
star

Sun Feb 06 2022 21:32:20 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting
star

Sun Feb 06 2022 21:21:32 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/sum-of-digits-of-a-number/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #digitssum
star

Sun Feb 06 2022 21:11:58 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #palindrome
star

Sun Feb 06 2022 21:09:41 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #naturalsum
star

Sun Feb 06 2022 21:03:20 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/fibonacci-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #fibonacci #n-thfibonacci #fibonacciseries
star

Sun Feb 06 2022 20:37:10 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/print-1-to-n-without-using-loops-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #print1ton using recursion
star

Sat Jan 08 2022 18:00:23 GMT+0000 (Coordinated Universal Time)

#recursion #arrays

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension