Grid Paths:

Given a grid of size n x n, find the number of paths from the top-left corner to the bottom-right corner, moving only right or down.

Pseudocode:

   dp[0][0] = 1
   for i from 1 to n:
       dp[0][i] = 1
       dp[i][0] = 1
   for i from 1 to n:
       for j from 1 to n:
           dp[i][j] = dp[i-1][j] + dp[i][j-1]
   return dp[n-1][n-1]
Minimum Path Sum:

Given a grid of size m x n, find the minimum sum of a path from the top-left corner to the bottom-right corner, moving only right or down.

Pseudocode:

   for i from 1 to m:
       grid[i][0] += grid[i-1][0]
   for j from 1 to n:
       grid[0][j] += grid[0][j-1]
   for i from 1 to m:
       for j from 1 to n:
           grid[i][j] += min(grid[i-1][j], grid[i][j-1])
   return grid[m-1][n-1]
Unique Paths with Obstacles:

Given a grid of size m x n with obstacles, find the number of unique paths from the top-left corner to the bottom-right corner, moving only right or down. Obstacles are represented by 1 and empty cells are represented by 0.

Pseudocode:

   if grid[0][0] == 1:
       return 0
   dp[0][0] = 1
   for i from 1 to m:
       if grid[i][0] == 0:
           dp[i][0] = dp[i-1][0]
   for j from 1 to n:
       if grid[0][j] == 0:
           dp[0][j] = dp[0][j-1]
   for i from 1 to m:
       for j from 1 to n:
           if grid[i][j] == 0:
               dp[i][j] = dp[i-1][j] + dp[i][j-1]
   return dp[m-1][n-1]
Maximal Square:

Given a grid of 0's and 1's, find the area of the largest square containing only 1's.

Pseudocode:

   max_side = 0
   for i from 0 to m:
       for j from 0 to n:
           if i == 0 or j == 0:
               dp[i][j] = grid[i][j]
           else if grid[i][j] == 1:
               dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
           max_side = max(max_side, dp[i][j])
   return max_side * max_side
These are just a few examples of dynamic programming algorithms on grids. There are many more variations and applications of dynamic programming on grids.

1.th-First Search (BFS):

   import java.util.*;

   public class BFS {
       public static Set<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
           Queue<Integer> queue = new LinkedList<>();
           Set<Integer> visited = new HashSet<>();
           queue.add(start);
           while (!queue.isEmpty()) {
               int vertex = queue.poll();
               if (!visited.contains(vertex)) {
                   visited.add(vertex);
                   for (int neighbor : graph.get(vertex)) {
                       queue.add(neighbor);
                   }
               }
           }
           return visited;
       }

       public static void main(String[] args) {
           Map<Integer, List<Integer>> graph = new HashMap<>();
           graph.put(0, Arrays.asList(1, 2));
           graph.put(1, Arrays.asList(2));
           graph.put(2, Arrays.asList(0, 3));
           graph.put(3, Arrays.asList(3));
           Set<Integer> visited = bfs(graph, 2);
           System.out.println(visited); // Output: [0, 2, 3, 1]
       }
   }
Depth-First Search (DFS):
   import java.util.*;

   public class DFS {
       public static void dfs(Map<Integer, List<Integer>> graph, int start, Set<Integer> visited) {
           visited.add(start);
           for (int neighbor : graph.get(start)) {
               if (!visited.contains(neighbor)) {
                   dfs(graph, neighbor, visited);
               }
           }
       }

       public static void main(String[] args) {
           Map<Integer, List<Integer>> graph = new HashMap<>();
           graph.put(0, Arrays.asList(1, 2));
           graph.put(1, Arrays.asList(2));
           graph.put(2, Arrays.asList(0, 3));
           graph.put(3, Arrays.asList(3));
           Set<Integer> visited = new HashSet<>();
           dfs(graph, 2, visited);
           System.out.println(visited); // Output: [0, 2, 3, 1]
       }
   }
Dijkstra's Algorithm:
   import java.util.*;

   public class Dijkstra {
       public static Map<Integer, Integer> dijkstra(Map<Integer, Map<Integer, Integer>> graph, int start) {
           Map<Integer, Integer> distances = new HashMap<>();
           for (int vertex : graph.keySet()) {
               distances.put(vertex, Integer.MAX_VALUE);
           }
           distances.put(start, 0);
           PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
           queue.add(new int[]{start, 0});
           while (!queue.isEmpty()) {
               int[] current = queue.poll();
               int vertex = current[0];
               int distance = current[1];
               if (distance > distances.get(vertex)) {
                   continue;
               }
               for (int neighbor : graph.get(vertex).keySet()) {
                   int newDistance = distance + graph.get(vertex).get(neighbor);
                   if (newDistance < distances.get(neighbor)) {
                       distances.put(neighbor, newDistance);
                       queue.add(new int[]{neighbor, newDistance});
                   }
               }
           }
           return distances;
       }

       public static void main(String[] args) {
           Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
           graph.put(0, new HashMap<>());
           graph.get(0).put(1, 4);
           graph.get(0).put(2, 1);
           graph.put(1, new HashMap<>());
           graph.get(1).put(3, 1);
           graph.get(1).put(2, 2);
           graph.put(2, new HashMap<>());
           graph.get(2).put(3, 5);
           Map<Integer, Integer> distances = dijkstra(graph, 0);
           System.out.println(distances); // Output: {0=0, 1=4, 2=1, 3=5}
       }
   }

# dp on strings
Given a string str, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Determine the fewest cuts needed for palindrome partitioning of the given string.


Example 1:

Input: str = "ababbbabbababa"
Output: 3
Explaination: After 3 partitioning substrings 
are "a", "babbbab", "b", "ababa".

static int palindromicPartition(String str)
    {
        List<List<String>> ans = new ArrayList<>(); 
        int n= str.length();
        int dp[][] = new int[n][n];
        // f(0,ans,str,new ArrayList<>(),dp,n);
        // return ans.size();
        int A[] = new int[n];
        for(int i=0;i<n;i++){
            A[i]=i;
            for(int j=0;j<=i;j++){
                if(isPalindrom(j,i,str,dp)){
                if(j==0) A[i]=0;
                else A[i]=Math.min(A[i],A[j-1]+1);
                }
            }
        }return A[n-1];
        
    }
    static void f(int i,List<List<String>> ans,String st,List<String> tem,int dp[][],int n){
        if(i==n){
            ans.add(new ArrayList<>(tem));
            return;
        }
        for(int j=i;j<n;j++){
            if(isPalindrom(i,j,st,dp)){
                tem.add(st.substring(i,j+1));
                f(j+1,ans,st,tem,dp,n);
                tem.remove(tem.size()-1);
            }
        }
            
    }
    static boolean isPalindrom(int i,int j,String s,int dp[][]){
        if(dp[i][j]!=0) return dp[i][j]==1;
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)) {
                 dp[i][j]=-1;
                 return false;
            }
            i++;
            j--;
        }
        dp[i][j]=1;
        return true;
    }



# greedy 

static int maxChildren(int N,int M,int g[], int sz[]) {
Arrays.sort(g);
Arrays.sort(sz);
int i=0;
for(int j=0;i<N && j<M;j++)
    if(sz[j]>=g[i])i++;
    return i;
  }
  

double fractionalKnapsack(int W, Item arr[], int n) 
    {
        Arrays.sort(arr,(a,b)->{
            double r2=((double)b.value/(double)b.weight);
            double r1=((double)a.value/(double)a.weight);
            return (r1<r2)?1:(r1>r2)?-1:0;
            });
        double ans =0,cur=0;
        for(int i=0;i<arr.length;i++){
            if(cur+arr[i].weight<=W){
                ans+=arr[i].value;
                cur+=arr[i].weight;
            }else {
                double rem= W-cur;
                ans+=(arr[i].value/(double)arr[i].weight) * rem;
                break;
            }
        }return ans;
    }

Given an infinite supply of each denomination of Indian currency { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } and a target value N.
Find the minimum number of coins and/or notes needed to make the change for Rs N. You must return the list containing the value of coins required. 


Example 1:

Input: N = 43
Output: 20 20 2 1
Explaination: 
Minimum number of coins and notes needed 
to make 43. 

static List<Integer> minPartition(int N)
    {
        // code here
        int A[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } ;
        List<Integer> ans = new ArrayList<>();
        for(int i=A.length-1;i>=0;i--){
            while(N>=A[i]){
                N-=A[i];
                ans.add(A[i]);
            }
        }return ans;
        
    }
You are a owner of lemonade island, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Given an integer array bills of size N where bills [ i ] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input:
N = 5
bills [ ] = {5, 5, 5, 10, 20}
Output: True
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change we return true.
 

Example 2:

Input:
N = 5
bills [ ] = {5, 5, 10, 10, 20}
Output: False

static boolean lemonadeChange(int N, int bills[]) {

        // code here

        int five_usd = 0;

        int ten_usd = 0;

        for(int i: bills){

            if(i == 5) five_usd++;

            else if(i == 10){

                five_usd--;

                ten_usd++;

            } else if(ten_usd > 0){

                ten_usd--;

                five_usd--;

            } else {

                five_usd -= 3;

            }

            if(five_usd < 0) return false;

        }

        return true;

    }
Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in exp.
For example, the function should return 'true' for exp = [()]{}{[()()]()} and 'false' for exp = [(]).

Note: The drive code prints "balanced" if function return true, otherwise it prints "not balanced".

Example 1:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balanced pairs, with 0 number of 
unbalanced bracket.
bool ispar(string x)
    {
        stack<char>st;
        for(int i=0;i<x.length();i++){
            if(!st.empty() && (st.top()==')'||st.top()==']'|| st.top()=='}')){
                return false;
            }else if(!st.empty() &&((st.top()=='(' && x[i]==')')||(st.top()=='{' && x[i]=='}')||(st.top()=='[' && x[i]==']'))){
                st.pop();
            }else{
                st.push(x[i]);
            }
        }
        // Your code here
       if(!st.size()){
           return true;
       }
       return false;
        
        
    }
 There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time?

Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.


Example 1:

Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] =  {2,4,6,7,9,9}
Output: 
4
Explanation:
Maximum four meetings can be held with
given start and end timings.
The meetings are - (1, 2),(3, 4), (5,7) and (8,9)

public static int maxMeetings(int start[], int end[], int n)
    {
        int meet[][] = new int[n][3];
        for(int i=0;i<n;i++){
            meet[i][0]=start[i];
            meet[i][1]=end[i];
            meet[i][2]=i;
        }
        int ans =1;
        Arrays.sort(meet,(a,b)->{//end time asc
            if(a[1]<b[1]) return -1;
            else if(a[1]>b[1]) return 1;
            else if(a[2]<b[2]) return -1;
            return 1;
        });
        int endp=meet[0][1];
        for(int i=1;i<n;i++){
            if(meet[i][0]>endp){
                endp=meet[i][1];
                ans++;
            }
        }
        
        return ans;
    }

Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.
Consider that all the trains arrive on the same day and leave on the same day. Arrival and departure time can never be the same for a train but we can have arrival time of one train equal to departure time of the other. At any given instance of time, same platform can not be used for both departure of a train and arrival of another train. In such cases, we need different platforms.


Example 1:

Input: n = 6 
arr[] = {0900, 0940, 0950, 1100, 1500, 1800}
dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation: 
Minimum 3 platforms are required to 
safely arrive and depart all trains.
Example 2:

Input: n = 3
arr[] = {0900, 1100, 1235}
dep[] = {1000, 1200, 1240}
Output: 1
Explanation: Only 1 platform is required to 
safely manage the arrival and 
static int findPlatform(int arr[], int dep[], int n)
    {
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i=1,j=0,cur=1,ans=0;
        while(i<n && j<n){
            if(arr[i]<=dep[j]){
                cur++;
                i++;
            }else if(arr[i]>dep[j]){
                cur--;
                j++;
            }
            ans =Math.max(ans,cur);
        }return ans;
    }
    Given a set of N jobs where each jobi has a deadline and profit associated with it.

Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline.

Find the number of jobs done and the maximum profit.

Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.


Example 1:

Input:
N = 4
Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output:
2 60
Explanation:
Job1 and Job3 can be done with
maximum profit of 60 (20+40).
Example 2:

Input:
N = 5
Jobs = {(1,2,100),(2,1,19),(3,2,27),
        (4,1,25),(5,1,15)}
Output:
2 127
Explanation:
2 jobs can be done with
maximum profit of 127 (100+27).
int[] JobScheduling(Job arr[], int n)
    {
        // Your code here
        Arrays.sort(arr,(a,b)->{
            if(a.profit>b.profit) return -1;
            else if(a.profit<b.profit) return 1;
            return 0;
        });
        int maxd=0,prof=0,ans=0;
        for(int i=0;i<n;i++) maxd=Math.max(maxd,arr[i].deadline);
        int fill[] = new int[maxd+1];
        for(int i=0;i<maxd+1;i++) fill[i]=-1;
        for(int i=0;i<n;i++){
            for(int j=arr[i].deadline;j>0;j--){
                if(fill[j]==-1){
                    fill[j]=i;
                    ans++;
                    prof+=arr[i].profit;
                    break;
                }
            }
        }return new int[]{ans,prof};
    }

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

Example 1:

Input:
Intervals = {{1,3},{2,4},{6,8},{9,10}}
Output: {{1, 4}, {6, 8}, {9, 10}}
Explanation: Given intervals: [1,3],[2,4]
[6,8],[9,10], we have only two overlapping
intervals here,[1,3] and [2,4]. Therefore
we will merge these two and return [1,4],
[6,8], [9,10].
Example 2:

Input:
Intervals = {{6,8},{1,9},{2,4},{4,7}}
Output: {{1, 9}}
public int[][] overlappedInterval(int[][] A)
    {
        Arrays.sort(A,(a,b)->a[0]-b[0]);
        List<int[]> tem = new ArrayList<>();
        int st=A[0][0];
        int en=A[0][1];
        for(int i=1;i<A.length;i++){
            if(A[i][0]<=en){
                en=Math.max(en,A[i][1]);
            }else {
                tem.add(new int[]{st,en});
                st=A[i][0];
                en=A[i][1];
            }
        }
        tem.add(new int[]{st,en});
        return tem.stream().toArray(int[][]::new);
    }

# recursion 

Your task  is to implement the function atoi. The function takes a string(str) as argument and converts it to an integer and returns it.

Note: You are not allowed to use inbuilt function.

Example 1:

Input:
str = 123
Output: 123
Example 2:

Input:
str = 21a
Output: -1
Explanation: Output is -1 as all
characters are not digit only.
int atoi(String str) {
	// Your code here
	int n=str.length();
	int ans=0,fl=-1,i=0;
	if(str.charAt(0)=='-'){
	    fl=0;
	    i=1;
	}
	for(;i<n;i++){
	    char cg =str.charAt(i);
	    if(cg>='a'&& cg<='z'|| cg=='-'|| cg=='+') return -1;
	    ans=ans*10+Integer.parseInt(cg+"");
	}return (fl==0)?-1*ans:ans;
    }

Given a number and its reverse. Find that number raised to the power of its own reverse.
Note: As answers can be very large, print the result modulo 109 + 7.

Example 1:

Input:
N = 2
Output: 4
Explanation: The reverse of 2 is 2
and after raising power of 2 by 2 
we get 4 which gives remainder as 
4 by dividing 1000000007.
Example 2:

Input:
N = 12
Output: 864354781
Explanation: The reverse of 12 is 21
and 1221 , when divided by 1000000007 
gives remainder as 864354781.

 long mod =(long)1e9+7;
    long power(int N,int R)
    {
        long ans =1;
        long te=R;
        // if(te<0) te=-1*te;
        while(te>0){
            if(te%2==1){
                ans =(ans*N)%mod;
                te-=1;
            }else{
                N=(N *N)%mod;
                te/=2;
            }
            
        }
        if(te<0) ans =(long)1/ans;
        return ans%mod;
        
    }
Given a string S, Find all the possible subsequences of the String in lexicographically-sorted order.

Example 1:

Input : str = "abc"
Output: a ab abc ac b bc c
Explanation : There are 7 subsequences that 
can be formed from abc.
Example 2:

Input: str = "aa"
Output: a a aa
Explanation : There are 3 subsequences that 
can be formed from aa.
 public List<String> AllPossibleStrings(String s)
    {
        // Code here
        List<String> ans = new ArrayList<>();
        for(int i=0;i<(1<<s.length());i++){//0 to 2^8-1
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<s.length();j++){//0 to len(s)
                if((i&(1<<j))!=0)sb.append(s.charAt(j));
            }
            if(sb.length()>0)//check for empty str
            ans.add(sb.toString());
        }
        Collections.sort(ans);
        return ans;
    }
Given a pair of strings, Geek wants to find the better string. The better string is the string having more number of distinct subsequences.

If both the strings have equal count of distinct subsequence then return str1.

Example 1:

Input:
str1 = "gfg", str2 = "ggg"
Output: "gfg"
Explanation: "gfg" have 7 distinct subsequences whereas "ggg" have 4 distinct subsequences. 
Example 2:

Input: str1 = "a", str2 = "b"
Output: "a"
Explanation: Both the strings have only 1 distinct subsequence.
public static String betterString(String s, String s2) {
        int dp[][] = new int[s.length()+1][s2.length()+1];
        for(int i=0;i<s.length();i++)Arrays.fill(dp[i],-1);
        int l1=memo(0,0,s,dp);
        dp= new int[s.length()][s2.length()];
        for(int i=0;i<s.length();i++)Arrays.fill(dp[i],-1);
        int l2=memo(0,0,s2,dp);
        return l1>l2?s: l1==l2? s: s2;
    }
    static int count()
    static int memo(int i,int j,String s,int dp[][]){
        if(i==s.length()||j==s.length()) return 1;
        if(dp[i][j]!=-1) return dp[i][j];
        if(i!=j && s.charAt(i)!=s.charAt(j)){
            dp[i][j]=memo(i+1,j,s,dp)+memo(i+1,j+1,s,dp);
        }else dp[i][j]=memo(i+1,j,s,dp);
        return dp[i][j];
    }
Given an array of integers and a sum B, find all unique combinations in the array where the sum is equal to B. The same number may be chosen from the array any number of times to make B.

Note:
        1. All numbers will be positive integers.
        2. Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
        3. The combinations themselves must be sorted in ascending order.


Example 1:

Input:
N = 4
arr[] = {7,2,6,5}
B = 16
Output:
(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)
Example 2:

Input:
N = 11
arr[] = {6,5,7,1,8,2,9,9,7,7,9}
B = 6
Output:
(1 1 1 1 1 1)
(1 1 1 1 2)
(1 1 2 2)
(1 5)
(2 2 2)
(6)
static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B)
    {
        ArrayList<ArrayList<Integer>>  ans = new ArrayList<>();
        f(0,A,B,ans,new ArrayList<>());
        return ans;
    }
    static void f(int i,ArrayList<Integer> A, int B,
    ArrayList<ArrayList<Integer>>  ans ,ArrayList<Integer> tem){
        if(i==A.size()){
            if(B==0){
                ans.add(new ArrayList<>(tem));
            }return;
        }
        if(A.get(i)<=B){
            tem.add(A.get(i));
            f(i+1,A,B-A.get(i),ans,tem);
            tem.remove(tem.size()-1);
        }
        f(i+1,A,B,ans,tem);
    }
You are given a collection of numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to the target. Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.


Example:

Input:  candidates = [10,1,2,7,6,1,5], target = 8. 
Output:  [[1,1,6], [1,2,5], [1,7], [2,6]]. 
Explanation:  These are the unique combinations whose sum is equal to the target.
public static List<List<Integer>> combinationSum2(int[] a, int s) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(a);
        f(0,a,s,ans,new ArrayList<>());
        return ans;
    }
    static void f(int ind,int a[],int t,List<List<Integer>> ans,ArrayList<Integer> tem){
        if(t==0){
            ans.add(new ArrayList<>(tem));
            return;
        } 
        for(int i=ind;i<a.length;i++){
            if(i>ind && a[i]==a[i-1]) continue;
            if(a[i]>t) break;
            tem.add(a[i]);
            f(i+1,a,t-a[i],ans,tem);
            tem.remove(tem.size()-1);
        }
    }
Given a list arr of N integers, print sums of all subsets in it.

 

Example 1:

Input:
N = 2
arr[] = {2, 3}
Output:
0 2 3 5
Explanation:
When no elements is taken then Sum = 0.
When only 2 is taken then Sum = 2.
When only 3 is taken then Sum = 3.
When element 2 and 3 are taken then 
Sum = 2+3 = 5.
Example 2:

Input:
N = 3
arr = {5, 2, 1}
Output:
0 1 2 3 5 6 7 8
ArrayList<Integer> subsetSums(ArrayList<Integer> arr, int N){
        // code here
         ArrayList<Integer>  ans = new ArrayList<>();
         rec(ans,0,0,N,arr);
         Collections.sort(ans);
         return ans;
    }
    void rec(ArrayList<Integer> ans,int i,int sum,int n,ArrayList<Integer> arr){
        if(i==n){
            ans.add(sum);
            return;
        }
        rec(ans,i+1,sum+arr.get(i),n,arr);
        rec(ans,i+1,sum,n,arr);
    }

You are given an integer array nums that may contain duplicates. Your task is to return all possible subsets. Return only unique subsets and they can be in any order.

Example:

Input: 
nums = [1,2,2] 
Output: 
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: 
We can have subsets ranging from length 0 to 3. which are listed above. Also the subset [1,2] appears twice but is printed only once as we require only unique subsets.

 public static ArrayList<ArrayList<Integer>> printUniqueSubsets(int[] nums) {
        ArrayList<ArrayList<Integer>>  ans = new ArrayList<>();
        Arrays.sort(nums);
        rec(0,nums,new ArrayList<>(),ans);
        return ans;
    }
    static void rec(int id,int A[],ArrayList<Integer> tem,ArrayList<ArrayList<Integer>>  ans){
        ans.add(new ArrayList<>(tem));
        for(int i=id;i<A.length;i++){
            if(i!=id && A[i]==A[i-1]) continue;//unique checlk
            tem.add(A[i]);
            rec(i+1,A,tem,ans);
            tem.remove(tem.size()-1);
        }
    }
# DFS 

// { Driver Code Starts
// Initial Template for Java
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            String[] s = br.readLine().trim().split(" ");
            int V = Integer.parseInt(s[0]);
            int E = Integer.parseInt(s[1]);
            ArrayList<ArrayList<Integer>> adj =
                new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < V; i++) adj.add(new ArrayList<Integer>());
            for (int i = 0; i < E; i++) {
                String[] S = br.readLine().trim().split(" ");
                int u = Integer.parseInt(S[0]);
                int v = Integer.parseInt(S[1]);
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
            Solution obj = new Solution();
            ArrayList<Integer> ans = obj.dfsOfGraph(V, adj);
            for (int i = 0; i < ans.size(); i++)
                System.out.print(ans.get(i) + " ");
            System.out.println();
        }
    }
}
// } Driver Code Ends


class Solution {
    // Function to return a list containing the DFS traversal of the graph.
    public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        // Code here
        ArrayList<Integer> dfsStore = new ArrayList<>();
        boolean vis[] = new boolean[V + 1];
        
        for(int i = 0; i < V; i++){
            if(vis[i] == false){
                dfs(i, vis, adj, dfsStore);
            }
        }
        return dfsStore;
    }
    public void dfs(int node, boolean vis[], ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> dfsStore){
        dfsStore.add(node);
        vis[node] = true;
        
        for(Integer i : adj.get(node)){
            if(vis[i] == false){
                dfs(i, vis, adj, dfsStore);
            }
        }
    }
}
ANALYSIS :-

Time Complexity :- BigO(N+E) Where N is the time taken for visiting N nodes and E is for travelling through adjacent nodes.

Space Complexity :- BigO(N+E) + O(N) + O(N) where Space for adjacency list, Array,Auxiliary space.

# BFS 

// { Driver Code Starts
// Initial Template for Java
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            String[] s = br.readLine().trim().split(" ");
            int V = Integer.parseInt(s[0]);
            int E = Integer.parseInt(s[1]);
            ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < V; i++) adj.add(i, new ArrayList<Integer>());
            for (int i = 0; i < E; i++) {
                String[] S = br.readLine().trim().split(" ");
                int u = Integer.parseInt(S[0]);
                int v = Integer.parseInt(S[1]);
                adj.get(u).add(v);
                // adj.get(v).add(u);
            }
            Solution obj = new Solution();
            ArrayList<Integer> ans = obj.bfsOfGraph(V, adj);
            for (int i = 0; i < ans.size(); i++)
                System.out.print(ans.get(i) + " ");
            System.out.println();
        }
    }
}
// } Driver Code Ends


class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        // Code here
        ArrayList<Integer> bfs = new ArrayList<>();
        boolean vis[] = new boolean[V + 1];
        Queue<Integer> q = new LinkedList<>();
                
                q.add(0);
                vis[0] = true;
                
                while(!q.isEmpty()){
                    Integer node = q.poll();
                    bfs.add(node);
                    
                    for(Integer it : adj.get(node)){
                        if(vis[it] == false){
                            q.add(it);
                            vis[it] = true;
                        }
                    }
                }
        return bfs;
    }
}
ANALYSIS :-

Time Complexity :- BigO(N+E) where N = Nodes , E = travelling through adjacent nodes

Space Complexity :- BigO(N+E) + O(N) + O(N) where Space for adjacency list, visited array, queue data structure
# Detect A Cycle In Undirected Graph {B F S}

Intuition: The intuition behind this is to check for the visited element if it is found again, this means the cycle is present in the given undirected graph.

for(i= 1->N)

{

if(!vis[i]) 

  if(cyclebfs(i)) // if cycle is found , we return true

                   Return True; 

}

Approach: 

For the first component, firstly we insert the first element of the graph by marking it as visited in the Queue having prev of the first element as -1. Now we pop out that element and traverse the adjacent element list for that and then insert the elements in the Queue and continue the process until no adjacent element is found for the present element. Here, we can see that no loop is formed. So, we return false for the first component.

For the second component, a similar process will be done as we have done for the first component. Here we will be able to see that when we come to 7, 8 is one of the next adjacent ones which matters to us, and also, it is already marked as positive. This means someone is linked already with this element. So, it forms a loop and we return true finally.

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
       
            int V = 5;
            ArrayList<ArrayList<Integer>>adj = new ArrayList<>();
            for(int i = 0; i < V; i++)
                adj.add(i, new ArrayList<Integer>());
                adj.get(0).add(1);
                adj.get(0).add(2);
                adj.get(2).add(3);
                adj.get(1).add(3);
                adj.get(2).add(4);

            Solution obj = new Solution();
            boolean ans = obj.isCycle(V, adj);
            if(ans)
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }


class Node {
    int first;
    int second;
    public Node(int first, int second) {
        this.first = first;
        this.second = second; 
    }
}
class Solution
{
   static boolean checkForCycle(ArrayList<ArrayList<Integer>> adj, int s,
            boolean vis[])
    {
       Queue<Node> q =  new LinkedList<>(); //BFS
       q.add(new Node(s, -1));
       vis[s] =true;
       
       while(!q.isEmpty())
       {
           int node = q.peek().first;
           int par = q.peek().second;
           q.remove(); 
           
           for(Integer it: adj.get(node))
           {
               if(vis[it]==false)  
               {
                   q.add(new Node(it, node));
                   vis[it] = true; 
               }
        
               else if(par != it) return true;
           }
       }
       
       return false;
    }
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj)
    {
        boolean vis[] = new boolean[V];
        Arrays.fill(vis,false);
        for(int i=0;i<V;i++)
            if(vis[i]==false) 
                if(checkForCycle(adj, i,vis)) 
                    return true;
    
        return false;
    }
}
Output:

Yes

Time Complexity: O(N+E),  N is the time taken and E is for traveling through adjacent nodes overall. 

Space Complexity: O(N+E) +  O(N) + O(N) , space for adjacent list , array and queue

took reference from striver sde sheet

Approach: Run a for loop from the first node to the last node and check if the node is visited. If it is not visited then call the function recursively which goes into the depth as known as DFS search and if you find a cycle you can say that there is a cycle in the graph.

Basically calling the isCyclic function with number of nodes and passing the graph
Traversing from 1 to number of nodes and checking for every node if it is unvisited
If the node is unvisited then call a function checkForCycle, that checks if there is a cycle and returns true if there is a cycle.
Now the function checkForCycle has the node and previous of the parent node. It will also have the visited array and the graph that has adjacency list
Mark it as visited and then traverse for its adjacency list using a for loop.
Calling DFS traversal if that node is unvisited call recursive function that checks if its a cycle and returns true
If the previously visited node and it is not equal to the parent we can say there is cycle again and will return true
Now if you have traveled for all adjacent nodes and all the DSF have been called and it never returned true that means we have done the DSF call entirely and now we can return false, that mean there is no DSF cycle

import java.util.*;
class GFG {
    public static void main(String[] args) {


        int V = 5;

        ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList < > ());
        }
        // edge 0---1
        adj.get(0).add(1);
        adj.get(1).add(0);

        // edge 1---2
        adj.get(1).add(2);
        adj.get(2).add(1);

        // adge 2--3
        adj.get(2).add(3);
        adj.get(3).add(2);

        // adge 3--4
        adj.get(3).add(4);
        adj.get(4).add(3);

        // adge 1--4
        adj.get(1).add(4);
        adj.get(4).add(1);


        Solution obj = new Solution();
        boolean ans = obj.isCycle(V, adj);
        if (ans == true) {
            System.out.println("Cycle Detected");
        } else {
            System.out.println("No Cycle Detected");

        }
    }
}


class Solution {
    public boolean checkForCycle(int node, int parent, boolean vis[], ArrayList < ArrayList 
    < Integer >> adj) {
        vis[node] = true;
        for (Integer it: adj.get(node)) {
            if (vis[it] == false) {
                if (checkForCycle(it, node, vis, adj) == true)
                    return true;
            } else if (it != parent)
                return true;
        }

        return false;
    }
    // 0-based indexing Graph
    public boolean isCycle(int V, ArrayList < ArrayList < Integer >> adj) {
        boolean vis[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (vis[i] == false) {
                if (checkForCycle(i, -1, vis, adj))
                    return true;
            }
        }

        return false;
    }
}
Output:

Cycle Detected

Time Complexity: O(N+E),  N is the time taken and E is for traveling through adjacent nodes overall. 

Space Complexity: O(N)

In the above diagram, let us say we start DFS from node 2 and we visit the nodes: 0, 1, 3, 4 and 5 through the edges: 2->0, 0->1, 1->3, 3->4 and 4->5. These edges become the forward edges in our DFS traversal of the graph which eventually form a DFS tree considering the forward edges only whereas the edges which were not the part of our DFS i.e 0->3 and 3->5 become the back edges.

We will be using an array of visited vertices during the DFS traversal to check for back edges, so whenever we find an edge that goes back to a vertex already in the visited array, we return true as a result that the graph contains a cycle.

Algorithm for the solution
Take the number of edges and vertices as user input.
Use vertex visited array and parent node to create a recursive function. 
Mark the current vertex as visited. 
Make recursive calls for all the unvisited adjacent vertices for the current vertex, and if any of these recursive functions return true, return true as the final answer.
If any adjacent vertex is already in the visited array, mark the answer as true.
Return false if none of the above steps returns true. 
Implementation of the solution
#include<bits/stdc++.h>
using namespace std;
//Class for the graph.
class graph
{
    int v;
    //Adjacency list.
    list<int> *adjacencylist;
    //Function to detectcycle.
    bool checkcycle2(int v, bool vertvisited[], int parentnode);
    public:
    graph(int v);
    void drawedge(int v, int u);
    bool checkcycle();
};
//Constructor for a graph with v nodes.
graph::graph(int v)
{
    this->v=v;
    adjacencylist= new list<int>[v];
}
//To add edges in the graph.
void graph::drawedge(int v, int u)
{
    adjacencylist[v].push_back(u);
    adjacencylist[u].push_back(v);
}
//Function to keep track of visited nodes.
bool graph::checkcycle2(int v, bool vertvisited[], int parentnode)
{
    //Marking the vertex as visited.
    vertvisited[v]=true;
    //Making recursive calls for the adjacent 
    //vertices and return true if any back edge is 
    //found.
    list<int>::iterator itr;
      for(itr=adjacencylist[v].begin();itr!=adjacencylist[v].end();++itr)
    {
        if (!vertvisited[*itr])
        {
            if(checkcycle2(*itr, vertvisited, v))
            {
                return true;
            }
        }
        else if (*itr != parentnode)
        {
           return true;
        }
    }
    return false;
}
bool graph::checkcycle()
{
    //Declare and initialise the visited and recursion stack array as false.
    bool *vertvisited=new bool[v];
    for(int i=0;i<v;i++)
    {
        vertvisited[i]=false;
    }
    //Call the "checkcycle2" function for cycle 
    //detection.
    for(int i=0;i<v;i++)
    {
        if(!vertvisited[i])
        {
        if(checkcycle2(i, vertvisited, -1))
        {
            return true;
        }
        }
    }
    return false;
}
//Driver function.
int main()
{
    graph g(6);
    g.drawedge(0, 1);
    g.drawedge(1, 5);
    g.drawedge(5, 4);
    g.drawedge(4, 0);
    g.drawedge(4, 3);
    g.drawedge(3, 2);
    g.drawedge(0, 2);
    //Function call and print the result.
    if(g.checkcycle())
        cout << "Graph is cyclic";
    else
        cout << "Graph is acyclic";
    return 0;
}
 

Output-

Graph is cyclic

Breadth-First Search (BFS):
import java.util.*;

public class BFS {
    public void bfs(int[][] graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int i = 0; i < graph.length; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
    }
}
Depth-First Search (DFS):
import java.util.*;

public class DFS {
    public void dfs(int[][] graph, int start) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.length];
        visited[start] = true;
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.print(node + " ");
            for (int i = 0; i < graph.length; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    stack.push(i);
                }
            }
        }
    }
}
Dijkstra's Algorithm:
import java.util.*;

public class Dijkstra {
    public void dijkstra(int[][] graph, int start) {
        int[] dist = new int[graph.length];
        boolean[] visited = new boolean[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        for (int i = 0; i < graph.length - 1; i++) {
            int u = minDistance(dist, visited);
            visited[u] = true;
            for (int v = 0; v < graph.length; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
        printDistances(dist);
    }

    private int minDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] <= min) {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void printDistances(int[] dist) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }
}
Bellman-Ford Algorithm:
import java.util.*;

public class BellmanFord {
    public void bellmanFord(int[][] graph, int start) {
        int[] dist = new int[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        for (int i = 0; i < graph.length - 1; i++) {
            for (int u = 0; u < graph.length; u++) {
                for (int v = 0; v < graph.length; v++) {
                    if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
        }
        printDistances(dist);
    }

    private void printDistances(int[] dist) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }
}

Minimum Spanning Tree (MST):
Prim's Algorithm:

import java.util.*;

public class Prim {
    public void prim(int[][] graph) {
        int[] parent = new int[graph.length];
        int[] key = new int[graph.length];
        boolean[] mstSet = new boolean[graph.length];
        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;
        parent[0] = -1;
        for (int i = 0; i < graph.length - 1; i++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;
            for (int v = 0; v < graph.length; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }
        printMST(parent, graph);
    }

    private int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < key.length; i++) {
            if (!mstSet[i] && key[i] < min) {
                min = key[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \t Weight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + " \t " + graph[i][parent[i]]);
        }
    }
}
Kruskal's Algorithm:

import java.util.*;

public class Kruskal {
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    public void kruskal(int[][] graph) {
        int V = graph.length;
        Edge[] edges = new Edge[V * V];
        int index = 0;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (graph[i][j] != 0) {
                    Edge edge = new Edge();
                    edge.src = i;
                    edge.dest = j;
                    edge.weight = graph[i][j];
                    edges[index++] = edge;
                }
            }
        }
        Edge[] result = new Edge[V];
        Arrays.sort(edges);
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
        }
        int e = 0;
        int i = 0;
        while (e < V - 1) {
            Edge nextEdge = edges[i++];
            int x = find(parent, nextEdge.src);
            int y = find(parent, nextEdge.dest);
            if (x != y) {
                result[e++] = nextEdge;
                parent[x] = y;
            }
        }
        printMST(result);
    }

    private int find(int[] parent, int i) {
        if (parent[i] == i) {
            return i;
        }
        return find(parent, parent[i]);
    }

    private void printMST(Edge[] result) {
        System.out.println("Edge \t Weight");
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i].src + " - " + result[i].dest + " \t " + result[i].weight);
        }
    }
}

Floyd-Warshall Algorithm:
The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices in a weighted graph. Here's an example implementation in Java:

public class FloydWarshall {
    public void shortestPath(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        printSolution(dist);
    }

    private void printSolution(int[][] dist) {
        System.out.println("Shortest distances between every pair of vertices:");
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist.length; j++) {
                if (dist[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}
Prim's Algorithm:
Prim's algorithm is used to find the minimum spanning tree of a weighted undirected graph. Here's an example implementation in Java:

public class PrimsAlgorithm {
    public void minimumSpanningTree(int[][] graph) {
        int V = graph.length;
        int[] parent = new int[V];
        int[] key = new int[V];
        boolean[] mstSet = new boolean[V];
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }
        key[0] = 0;
        parent[0] = -1;
        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }
        printMST(parent, graph);
    }

    private int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < key.length; i++) {
            if (!mstSet[i] && key[i] < min) {
                min = key[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \t Weight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + " \t " + graph[i][parent[i]]);
        }
    }
}

Kruskal's Algorithm:
Kruskal's algorithm is also used to find the minimum spanning tree of a weighted undirected graph. Here's an example implementation in Java:

public class KruskalsAlgorithm {
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    public void minimumSpanningTree(int[][] graph) {
        int V = graph.length;
        Edge[] edges = new Edge[V * V];
        int index = 0;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (graph[i][j] != 0) {
                    Edge edge = new Edge();
                    edge.src = i;
                    edge.dest = j;
                    edge.weight = graph[i][j];
                    edges[index++] = edge;
                }
            }
        }
        Edge[] result = new Edge[V];
        Arrays.sort(edges);
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
        }
        int e = 0;
        for (int i = 0; i < edges.length && e < V - 1; i++) {
            Edge edge = edges[i];
            int x = find(parent, edge.src);
            int y = find(parent, edge.dest);
            if (x != y) {
                result[e++] = edge;
                parent[x] = y;
            }
        }
        printMST(result);
    }

    private int find(int[] parent, int i) {
        if (parent[i] == i) {
            return i;
        }
        return find(parent, parent[i]);
    }

    private void printMST(Edge[] result) {
        System.out.println("Edge \t Weight");
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i].src + " - " + result[i].dest + " \t " + result[i].weight);
        }
    }
}

Topological Sort:
import java.util.*;

public class TopologicalSort {
    public int[] sort(int[][] graph) {
        int V = graph.length;
        int[] inDegree = new int[V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (graph[i][j] != 0) {
                    inDegree[j]++;
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        int[] result = new int[V];
        int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            for (int i = 0; i < V; i++) {
                if (graph[node][i] != 0) {
                    inDegree[i]--;
                    if (inDegree[i] == 0) {
                        queue.offer(i);
                    }
                }
            }
        }
        return result;
    }
}
Strongly Connected Components (SCC):
import java.util.*;

public class SCC {
    private int V;
    private List<Integer>[] graph;
    private List<Integer>[] reverseGraph;
    private boolean[] visited;
    private Stack<Integer> stack;

    public SCC(int V) {
        this.V = V;
        graph = new ArrayList[V];
        reverseGraph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }
        visited = new boolean[V];
        stack = new Stack<>();
    }

    public void addEdge(int u, int v) {
        graph[u].add(v);
        reverseGraph[v].add(u);
    }

    public List<List<Integer>> getSCCs() {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        visited = new boolean[V];
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                List<Integer> scc = new ArrayList<>();
                reverseDfs(node, scc);
                result.add(scc);
            }
        }
        return result;
    }

    private void dfs(int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
        stack.push(node);
    }

    private void reverseDfs(int node, List<Integer> scc) {
        visited[node] = true;
        scc.add(node);
        for (int neighbor : reverseGraph[node]) {
            if (!visited[neighbor]) {
                reverseDfs(neighbor, scc);
            }
        }
    }
}
here are some common ways to use segment trees to solve problems:

Range Sum Queries:
A segment tree can be used to efficiently answer range sum queries on an array. The tree is built by recursively dividing the array into two halves and storing the sum of each segment in the corresponding node of the tree. To answer a range sum query, we traverse the tree and add up the sums of the segments that overlap with the query range.

Range Minimum Queries:
A segment tree can also be used to efficiently answer range minimum queries on an array. The tree is built by recursively dividing the array into two halves and storing the minimum value of each segment in the corresponding node of the tree. To answer a range minimum query, we traverse the tree and find the minimum value of the segments that overlap with the query range.

Lazy Propagation:
Lazy propagation is a technique used to update a segment tree efficiently when there are many updates to be made. Instead of updating all the nodes in the tree, we only update the nodes that are affected by the update and mark the other nodes as "lazy". When we need to query the tree, we first propagate the lazy updates to the affected nodes and then traverse the tree as usual.

Range Updates:
A segment tree can be used to efficiently update a range of values in an array. The tree is built by recursively dividing the array into two halves and storing the sum of each segment in the corresponding node of the tree. To update a range of values, we traverse the tree and update the nodes that overlap with the range.

Range Queries on Trees:
A segment tree can be used to efficiently answer range queries on trees. The tree is built by recursively dividing the tree into subtrees and storing the sum of each subtree in the corresponding node of the tree. To answer a range query on the tree, we traverse the tree and add up the sums of the subtrees that overlap with the query range.

Persistent Segment Trees:
A persistent segment tree is a data structure that allows us to efficiently store and query multiple versions of a segment tree. Instead of modifying the original tree, we create a new tree for each update and link it to the previous tree. This allows us to query any version of the tree without affecting the other versions.

Range Sum Queries:
public class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[2 * n];
        buildTree(nums);
    }

    private void buildTree(int[] nums) {
        for (int i = n; i < 2 * n; i++) {
            tree[i] = nums[i - n];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    public void update(int index, int val) {
        index += n;
        tree[index] = val;
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            tree[index / 2] = tree[left] + tree[right];
            index /= 2;
        }
    }

    public int sumRange(int left, int right) {
        left += n;
        right += n;
        int sum = 0;
        while (left <= right) {
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
            }
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }
}
Range Minimum Queries:
public class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[2 * n];
        buildTree(nums);
    }

    private void buildTree(int[] nums) {
        for (int i = n; i < 2 * n; i++) {
            tree[i] = nums[i - n];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = Math.min(tree[2 * i], tree[2 * i + 1]);
        }
    }

    public void update(int index, int val) {
        index += n;
        tree[index] = val;
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            tree[index / 2] = Math.min(tree[left], tree[right]);
            index /= 2;
        }
    }

    public int minRange(int left, int right) {
        left += n;
        right += n;
        int min = Integer.MAX_VALUE;
        while (left <= right) {
            if (left % 2 == 1) {
                min = Math.min(min, tree[left]);
                left++;
            }
            if (right % 2 == 0) {
                min = Math.min(min, tree[right]);
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return min;
    }
}

here's the complete code for lazy propagation:

public class SegmentTree {
    private int[] tree;
    private int[] lazy;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        lazy = new int[4 * n];
        buildTree(nums, 1, 0, n - 1);
    }

    private void buildTree(int[] nums, int index, int left, int right) {
        if (left == right) {
            tree[index] = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(nums, 2 * index, left, mid);
        buildTree(nums, 2 * index + 1, mid + 1, right);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public void update(int left, int right, int val) {
        update(1, 0, n - 1, left, right, val);
    }

    private void update(int index, int left, int right, int rangeLeft, int rangeRight, int val) {
        if (lazy[index] != 0) {
            tree[index] += lazy[index] * (right - left + 1);
            if (left != right) {
                lazy[2 * index] += lazy[index];
                lazy[2 * index + 1] += lazy[index];
            }
            lazy[index] = 0;
        }
        if (left > rangeRight || right < rangeLeft) {
            return;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            tree[index] += val * (right - left + 1);
            if (left != right) {
                lazy[2 * index] += val;
                lazy[2 * index + 1] += val;
            }
            return;
        }
        int mid = (left + right) / 2;
        update(2 * index, left, mid, rangeLeft, rangeRight, val);
        update(2 * index + 1, mid + 1, right, rangeLeft, rangeRight, val);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public int sumRange(int left, int right) {
        return sumRange(1, 0, n - 1, left, right);
    }

    private int sumRange(int index, int left, int right, int rangeLeft, int rangeRight) {
        if (lazy[index] != 0) {
            tree[index] += lazy[index] * (right - left + 1);
            if (left != right) {
                lazy[2 * index] += lazy[index];
                lazy[2 * index + 1] += lazy[index];
            }
            lazy[index] = 0;
        }
        if (left > rangeRight || right < rangeLeft) {
            return 0;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            return tree[index];
        }
        int mid = (left + right) / 2;
        int leftSum = sumRange(2 * index, left, mid, rangeLeft, rangeRight);
        int rightSum = sumRange(2 * index + 1, mid + 1, right, rangeLeft, rangeRight);
        return leftSum + rightSum;
    }
}
here's the complete code for range updates:

public class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        buildTree(nums, 1, 0, n - 1);
    }

    private void buildTree(int[] nums, int index, int left, int right) {
        if (left == right) {
            tree[index] = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(nums, 2 * index, left, mid);
        buildTree(nums, 2 * index + 1, mid + 1, right);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public void update(int left, int right, int val) {
        update(1, 0, n - 1, left, right, val);
    }

    private void update(int index, int left, int right, int rangeLeft, int rangeRight, int val) {
        if (left > rangeRight || right < rangeLeft) {
            return;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            tree[index] += val * (right - left + 1);
            if (left != right) {
                update(2 * index, left, (left + right) / 2, rangeLeft, rangeRight, val);
                update(2 * index + 1, (left + right) / 2 + 1, right, rangeLeft, rangeRight, val);
            }
            return;
        }
        update(2 * index, left, (left + right) / 2, rangeLeft, rangeRight, val);
        update(2 * index + 1, (left + right) / 2 + 1, right, rangeLeft, rangeRight, val);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public int sumRange(int left, int right) {
        return sumRange(1, 0, n - 1, left, right);
    }

    private int sumRange(int index, int left, int right, int rangeLeft, int rangeRight) {
        if (left > rangeRight || right < rangeLeft) {
            return 0;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            return tree[index];
        }
        int mid = (left + right) / 2;
        int leftSum = sumRange(2 * index, left, mid, rangeLeft, rangeRight);
        int rightSum = sumRange(2 * index + 1, mid + 1, right, rangeLeft, rangeRight);
        return leftSum + rightSum;
    }
}
here's the complete code for range queries on trees:

public class SegmentTree {
    private List<Integer>[] tree;
    private int[] start;
    private int[] end;
    private int[] treeIndex;
    private int[] flatTree;
    private int index;

    public SegmentTree(List<Integer>[] tree) {
        int n = tree.length;
        this.tree = tree;
        start = new int[n];
        end = new int[n];
        treeIndex = new int[n];
        flatTree = new int[4 * n];
        index = 0;
        dfs(0, -1);
        buildTree(1, 0, n - 1);
    }

    private void dfs(int node, int parent) {
        start[node] = index;
        treeIndex[index] = node;
        index++;
        for (int neighbor : tree[node]) {
            if (neighbor != parent) {
                dfs(neighbor, node);
            }
        }
        end[node] = index - 1;
    }

    private void buildTree(int index, int left, int right) {
        if (left == right) {
            flatTree[index] = treeIndex[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(2 * index, left, mid);
        buildTree(2 * index + 1, mid + 1, right);
        int leftNode = flatTree[2 * index];
        int rightNode = flatTree[2 * index + 1];
        flatTree[index] = (start[leftNode] < start[rightNode]) ? leftNode : rightNode;
    }

    public int query(int left, int right) {
        int nodeIndex = query(1, 0, tree.length - 1, left, right);
        return treeIndex[nodeIndex];
    }

    private int query(int index, int left, int right, int rangeLeft, int rangeRight) {
        if (left > rangeRight || right < rangeLeft) {
            return -1;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            return flatTree[index];
        }
        int mid = (left + right) / 2;
        int leftNode = query(2 * index, left, mid, rangeLeft, rangeRight);
        int rightNode = query(2 * index + 1, mid + 1, right, rangeLeft, rangeRight);
        if (leftNode == -1) {
            return rightNode;
        }
        if (rightNode == -1) {
            return leftNode;
        }
        return (start[leftNode] < start[rightNode]) ? leftNode : rightNode;
    }
}

Persistent Segment Tree for Range Sum Queries:
public class PersistentSegmentTree {
    private Node[] versions;
    private int versionCount;

    public PersistentSegmentTree(int[] nums) {
        int n = nums.length;
        versions = new Node[4 * n * (int) Math.ceil(Math.log(n) / Math.log(2))];
        versionCount = 0;
        buildTree(nums, 0, n - 1, 0);
    }

    private void buildTree(int[] nums, int left, int right, int index) {
        versions[index] = new Node();
        if (left == right) {
            versions[index].sum = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(nums, left, mid, 2 * index + 1);
        buildTree(nums, mid + 1, right, 2 * index + 2);
        versions[index].sum = versions[2 * index + 1].sum + versions[2 * index + 2].sum;
    }

    public int query(int version, int left, int right) {
        return query(version, 0, versions.length / 4 - 1, left, right, 0);
    }

    private int query(int version, int left, int right, int rangeLeft, int rangeRight, int index) {
        if (left > rangeRight || right < rangeLeft) {
            return 0;
        }
        if (left >= rangeLeft && right <= rangeRight) {
            return versions[version].sum - versions[index].sum;
        }
        int mid = (left + right) / 2;
        int leftSum = query(version, left, mid, rangeLeft, rangeRight, 2 * index + 1);
        int rightSum = query(version, mid + 1, right, rangeLeft, rangeRight, 2 * index + 2);
        return leftSum + rightSum;
    }

    public int update(int version, int index, int val) {
        versions = Arrays.copyOf(versions, versions.length + 1);
        versionCount++;
        update(version, 0, versions.length / 4 - 1, index, val, versionCount - 1);
        return versionCount - 1;
    }

    private void update(int version, int left, int right, int index, int val, int newVersion) {
        versions[newVersion] = new Node();
        if (left == right) {
            versions[newVersion].sum = val;
            return;
        }
        int mid = (left + right) / 2;
        if (index <= mid) {
            versions[newVersion].right = versions[version].right;
            update(versions[version].left, left, mid, index, val, versions[newVersion].left = versionCount);
        } else {
            versions[newVersion].left = versions[version].left;
            update(versions[version].right, mid + 1, right, index, val, versions[newVersion].right = versionCount);
        }
        versions[newVersion].sum = versions[versions[newVersion].left].sum + versions[versions[newVersion].right].sum;
    }

    private static class Node {
        int sum;
        int left;
        int right;

        public Node() {
            sum = 0;
            left = -1;
            right = -1;
        }
    }
}
Example usage:

int[] nums = {1, 3, 5, 7, 9};
PersistentSegmentTree pst = new PersistentSegmentTree(nums);
int version1 = 0;
int version2 = pst.update(version1, 2, 6);
int version3 = pst.update(version2, 3, 8);
System.out.println(pst.query(version1, 1, 3)); // Output: 8
System.out.println(pst.query(version2, 1, 3)); // Output: 11
System.out.println(pst.query(version3, 1, 3)); // Output: 13

M coloring 
public boolean graphColoring(boolean graph[][], int m, int n) {
        int col[] = new int[n];
        if(solve(0,graph,m,n,col)) return true;
        return false;
    }
    boolean solve(int node,boolean G[][],int m,int n,int[] col){
        if(node==n)return true;
        for(int c=1;c<=m;c++){// check all colors
            if(safe(node,G,c,col,n)){//check is safe 
                col[node]=c;
                if(solve(node+1,G,m,n,col)) return true;
                col[node]=0;
            }
        }return false;
    }
    boolean safe(int node,boolean G[][],int c,int col[],int n){
        for(int k=0;k<n;k++){
            if(k!=node && G[k][node] && col[k]==c) return false;
        }return true;
    }
# sudoko
static boolean SolveSudoku(int grid[][])
    {
        // add your code here
        return solve(grid);
    }
    static boolean solve(int grid[][]){
        int n=grid.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    for(int k=1;k<=n;k++){
                        if(isSafe(grid,k,n,i,j)){
                            grid[i][j]=k;
                            if(solve(grid))return true;
                            else grid[i][j]=0;//wrong choise
                        }
                    }return false;//we can't placed key
                }
            }
        }return true;
    }
    static boolean isSafe(int grid[][],int k,int n,int row,int col){
        for(int i=0;i<n;i++){
            if(grid[i][col]==k) return false;
            if(grid[row][i]==k) return false;
            if(grid[3*(row/3)+i/3][3*(col/3)+i%3]==k) return false;
        }return true;
    }
    
    //Function to print grids of the Sudoku.
    static void printGrid (int grid[][])
    {
        int n=grid.length;
        // add your code here
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(grid[i][j]+" ");
            }
        }
    }

# POWER SET
public List<String> AllPossibleStrings(String s)
    {
        // Code here
        List<String> ans = new ArrayList<>();
        for(int i=0;i<(1<<s.length());i++){//0 to 2^8-1
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<s.length();j++){//0 to len(s)
                if((i&(1<<j))!=0)sb.append(s.charAt(j));//
            }
            if(sb.length()>0)//check for empty str
            ans.add(sb.toString());
        }
        Collections.sort(ans);
        return ans;
    }

This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.

Subsets : https://leetcode.com/problems/subsets/

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 
Permutations : https://leetcode.com/problems/permutations/

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 
Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}
Combination Sum : https://leetcode.com/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}
Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
} 
Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/

public List<List<String>> partition(String s) {
   List<List<String>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), s, 0);
   return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
   if(start == s.length())
      list.add(new ArrayList<>(tempList));
   else{
      for(int i = start; i < s.length(); i++){
         if(isPalindrome(s, start, i)){
            tempList.add(s.substring(start, i + 1));
            backtrack(list, tempList, s, i + 1);
            tempList.remove(tempList.size() - 1);
         }
      }
   }
}

public boolean isPalindrome(String s, int low, int high){
   while(low < high)
      if(s.charAt(low++) != s.charAt(high--)) return false;
   return true;
}

This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.

Subsets : https://leetcode.com/problems/subsets/

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 
Permutations : https://leetcode.com/problems/permutations/

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 
Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}
Combination Sum : https://leetcode.com/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}
Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
} 
Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/

public List<List<String>> partition(String s) {
   List<List<String>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), s, 0);
   return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
   if(start == s.length())
      list.add(new ArrayList<>(tempList));
   else{
      for(int i = start; i < s.length(); i++){
         if(isPalindrome(s, start, i)){
            tempList.add(s.substring(start, i + 1));
            backtrack(list, tempList, s, i + 1);
            tempList.remove(tempList.size() - 1);
         }
      }
   }
}

public boolean isPalindrome(String s, int low, int high){
   while(low < high)
      if(s.charAt(low++) != s.charAt(high--)) return false;
   return true;
}

Question wants us to return the length of new array after removing duplicates and that we don't care about what we leave beyond new length , hence we can use i to keep track of the position and update the array.

Remove Duplicates from Sorted Array(no duplicates) :

public int removeDuplicates(int[] nums) {
    int i = 0;
    for(int n : nums)
        if(i < 1 || n > nums[i - 1]) 
            nums[i++] = n;
    return i;
}
Remove Duplicates from Sorted Array II (allow duplicates up to 2):

public int removeDuplicates(int[] nums) {
   int i = 0;
   for (int n : nums)
      if (i < 2 || n > nums[i - 2])
         nums[i++] = n;
   return i;
}

I will show you all how to tackle various tree questions using iterative inorder traversal. First one is the standard iterative inorder traversal using stack. Hope everyone agrees with this solution.

Question : Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}
Now, we can use this structure to find the Kth smallest element in BST.

Question : Kth Smallest Element in a BST

 public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }
We can also use this structure to solve BST validation question.

Question : Validate Binary Search Tree

public boolean isValidBST(TreeNode root) {
   if (root == null) return true;
   Stack<TreeNode> stack = new Stack<>();
   TreeNode pre = null;
   while (root != null || !stack.isEmpty()) {
      while (root != null) {
         stack.push(root);
         root = root.left;
      }
      root = stack.pop();
      if(pre != null && root.val <= pre.val) return false;
      pre = root;
      root = root.right;
   }
   return true;
}

Combination Sum I

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
    if (remain < 0) return; /** no solution */
    else if (remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for (int i = start; i < cand.length; i++) { 
            tempList.add(cand[i]);
            backtrack(list, tempList, cand, remain-cand[i], i);
            tempList.remove(tempList.size()-1);
        } 
    }

}
Combination Sum II

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
   List<List<Integer>> list = new LinkedList<List<Integer>>();
   Arrays.sort(candidates);
   backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
   
   if(remain < 0) return; /** no solution */
   else if(remain == 0) list.add(new ArrayList<>(tempList));
   else{
      for (int i = start; i < cand.length; i++) {
         if(i > start && cand[i] == cand[i-1]) continue; /** skip duplicates */
         tempList.add(cand[i]);
         backtrack(list, tempList, cand, remain - cand[i], i+1);
         tempList.remove(tempList.size() - 1);
      }
   }
}
Combination Sum III

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<Integer>(), k, n, 1);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
    if(tempList.size() > k) return; /** no solution */
    else if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for (int i = start; i <= 9; i++) {
            tempList.add(i);
            backtrack(list, tempList, k, remain-i, i+1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

Postorder traversal : Binary Tree Postorder Traversal

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()){
        root = stack.pop();
        list.add(0, root.val);
        if(root.left != null) stack.push(root.left);
        if(root.right != null) stack.push(root.right);
    }
    return list;
}
Preorder traversal : Binary Tree Preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()){
        root = stack.pop();
        list.add(root.val);
        if(root.right != null) stack.push(root.right);
        if(root.left != null) stack.push(root.left);
    }
    return list;
}
Inorder traversal : Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
    }
    return list;
}

# power set 

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // Arrays.sort(nums);
        // dfs(ans,new ArrayList<>(),nums,0);
        // return ans;   
        int n = nums.length;
        for(int i=(1<<n);i<(1<<(n+1));i++){
            String bitmask = Integer.toBinaryString(i).substring(1);
            List<Integer> tem = new ArrayList<>();
            for(int j=0;j<n;j++){
                if(bitmask.charAt(j)=='1')tem.add(nums[j]);
            }ans.add(tem);
        }return ans;
    }
    private void dfs(List<List<Integer>> ans,List<Integer> tem, int A[],int i){
        ans.add(new ArrayList<>(tem));
        for(int j=i;j<A.length;j++){
            tem.add(A[j]);
            dfs(ans,tem,A,j+1);
            tem.remove(tem.size()-1);
        }
    }
}

# partition dp 

static int matrixMultiplication(int N, int A[])
    {
        // code here
        int dp[][] = new int[N][N];
        return f(1,N-1,A,dp);
    }
    static int f(int i,int j,int A[],int dp[][]){
        if(i==j) return 0;
        if(dp[i][j]!=0) return dp[i][j];
        int min=(int)1e9;
        for(int k=i;k<=j-1;k++){
            int step = A[i-1]*A[k]*A[j]+f(i,k,A,dp)+f(k+1,j,A,dp);
            min=Math.min(min,step);
        }return dp[i][j]= min;
    }

Partition DP is a technique used to solve problems that involve partitioning a set of elements into two or more subsets, such that each subset satisfies certain conditions. The basic idea behind partition DP is to define a state that represents the current state of the partition and then recursively compute the optimal solution for that state.

The rules for partition DP are as follows:

Define the state: The first step in partition DP is to define a state that represents the current state of the partition. The state should be defined in such a way that it captures all the relevant information about the current partition.

Define the base case: The next step is to define the base case for the partition. This is the simplest possible partition that can be solved directly without any recursion.

Define the recurrence relation: The recurrence relation defines how to compute the optimal solution for the current state of the partition, based on the optimal solutions for the previous states. The recurrence relation should be defined in such a way that it captures the optimal solution for the current state, based on the optimal solutions for the previous states.

Compute the optimal solution: Once the recurrence relation has been defined, the optimal solution for the current state can be computed by recursively applying the recurrence relation to the previous states, until the base case is reached.

Return the final solution: Once the optimal solution for the current state has been computed, it can be returned as the final solution to the problem.

Partition DP can be used to solve a wide range of problems, including subset sum, knapsack, and graph partitioning problems. The key to using partition DP effectively is to carefully define the state and the recurrence relation, so that they capture all the relevant information about the problem and lead to an efficient solution.

# identity
Partition DP problems typically involve partitioning a set of elements into two or more subsets, such that each subset satisfies certain conditions. Here are some common characteristics of partition DP problems:

The problem involves partitioning a set of elements into two or more subsets.

The subsets must satisfy certain conditions, such as having a certain sum, size, or property.

The problem requires finding the optimal partition that satisfies the conditions.

The problem may involve finding the number of ways to partition the set, or the actual partition itself.

The problem may involve finding the minimum or maximum value of a certain function over all possible partitions.

The problem may involve finding the optimal partition recursively, by considering all possible partitions of a smaller subset of elements.

Some examples of partition DP problems include:

Subset sum problem: Given a set of integers, find if there exists a subset whose sum is equal to a given target value.

Knapsack problem: Given a set of items with weights and values, find the maximum value that can be obtained by selecting a subset of items that fit into a knapsack of a given capacity.

Graph partitioning problem: Given a graph, partition the vertices into two or more subsets such that the number of edges between the subsets is minimized.

Balanced partition problem: Given a set of integers, partition the set into two subsets such that the difference between the sums of the subsets is minimized.

If a problem involves partitioning a set of elements and finding the optimal partition that satisfies certain conditions, it may be a partition DP problem.

static int matrixMultiplication(int N, int A[])
    {
        int dp[][] = new int[N][N];
        for(int i=N-1;i>=1;i--){
            for(int j=i+1;j<N;j++){
                int min=(int)1e9;
                for(int k=i;k<=j-1;k++){
                    int step = A[i-1]*A[k]*A[j]+
                    dp[i][k]+dp[k+1][j];
                    min=Math.min(min,step);
                } dp[i][j]= min;
            }
        }
        return dp[1][N-1];
    }
    static int f(int i,int j,int A[],int dp[][]){
        if(i==j) return 0;
        if(dp[i][j]!=0) return dp[i][j];
        int min=(int)1e9;
        for(int k=i;k<=j-1;k++){
            int step = A[i-1]*A[k]*A[j]+f(i,k,A,dp)+f(k+1,j,A,dp);
            min=Math.min(min,step);
        }return dp[i][j]= min;
    }

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {

		int n = nums.size();

		vector<int>LIS(n+1, 1);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j])
					LIS[i] = max(LIS[i], 1 + LIS[j]);
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++) {
			ans = max(ans, LIS[i]);
		}

		return ans;
	}
};

class Solution {
public:
	bool canPartition(vector<int>& nums) {

		int n = nums.size();

		int sum = 0;
		for (int i = 0; i < n; i++)
			sum += nums[i];

		if (sum % 2 != 0) return false;

		int target = sum/2;
		vector<bool>dp(target+1, false);

		dp[0] = true;
		for (int i = 0; i < n; i++) {
			for (int j = target; j >= nums[i]; j--) {
				dp[j] = dp[j] | dp[j - nums[i]];
			}
		}

		return dp[target];
	}
};

class Solution {
	int dp[(1<<16) + 2];
public:
	bool canPartitionKSubsets(vector<int>& nums, int k) {

		int n = nums.size();

		fill(dp, dp+(1<<16)+2, -1);

		int sum = 0;
		for (int i = 0; i < n; i++)
			sum += nums[i];

		if (sum % k != 0) return false;

		int target = sum/k;

		dp[0] = 0;
		for (int mask = 0; mask < (1<<n); mask++) {
			if (dp[mask] == -1) continue;
			for (int i = 0; i < n; i++) {
				if (!(mask & (1 << i)) && dp[mask] + nums[i] <= target)
					dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target;
			}
		}

		return dp[(1<<n)-1] == 0;
	}
};

class Solution {
	int longestCommonSubsequenceUtil(string text1, string text2, int n, int m) {
		if (n == 0 || m == 0)
			return 0;

		vector<vector<int>>L(n+1, vector<int>(m+1, 0));

		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				if (i == 0 || j == 0)
					L[i][j] = 0;
				else if (text1[i-1] == text2[j-1])
					L[i][j] = 1 + L[i-1][j-1];
				else
					L[i][j] = max(L[i][j-1], L[i-1][j]);
			}
		}

		return L[n][m];
	}

public:
	int longestCommonSubsequence(string text1, string text2) {
		int n = text1.size();
		int m = text2.size();

		return longestCommonSubsequenceUtil(text1, text2, n, m);
	}
};

class Solution {
public:
	int minCut(string s) {

		int n = s.length();

		int res[n];
		bool P[n][n];

		for (int i = 0; i < n; i++)
			P[i][i] = true;


		for (int L = 2; L <= n; L++) {
			for (int i = 0; i < n-L+1; i++) {
				int j = i+L-1;

				if (L == 2) {
					P[i][j] = (s[i] == s[j]);
				} else {
					P[i][j] = (s[i] == s[j]) && P[i+1][j-1];
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (P[0][i])
				res[i] = 0;
			else {
				res[i] = INT_MAX;
				for (int j = 0; j < i; j++) {
					if (P[j+1][i] && res[i] > 1 + res[j])
						res[i] = 1+res[j];
				}
			}
		}

		return res[n-1] == INT_MAX ? 1 : res[n-1];
	}
};