DP

[Khandagale-Saurabh]

Pattern Dp: Subset=> https://leetcode.com/problems/count-sorted-vowel-strings/solutions/1207519/java-3-methods-time-beats-100/ initilize with 1,1 for both j=0 ||i==0 dp[i][j]=dp[i-1][j]+dp[i][j-1];

LCM

[Khandagale-Saurabh]

Q] Coin Change [Combination]

outter loop coin k liye and inner loop dp k liye remeber ki inner loop vaha se start karo jaha coin ho

[Khandagale-Saurabh]

Q 1]Knap Sack

Q]go back to weight

Q2] Subset sum [T/F] weight k array se compare karo

agar array ka size 0, hai toh min 0 create kr sakta hai [T] => True agar array ka size weight 1,2..nth hai kya a 0 size k wait mai rakh sakta hai kya??: No => False

=> change from knapsak weight ko arrya and Max to replace kiya || se

static boolean isThereSubsetSum(int arr[], int n, int sum) {
  boolean dp[][] = new boolean[n + 1][sum + 1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;

  for (int i = 1; i <= sum; i++)
    dp[0][i] = false;

  for (int i = 1; i <= sum; i++) {
    for (int j = 1; j <= n; j++) {
      if (j < arr[i - 1])
        dp[i][j] = dp[i - 1][j];
      if (j >= arr[i - 1])
        dp[i][j] = dp[i - 1][j] ||
        dp[i - 1][j - arr[i - 1]];
    }
  }
  return dp[n][sum];
}

[Khandagale-Saurabh]

Q3] Equal Sum Partition [T/F] => agar sum /targer even hai toh sum ko divide karo aur subset sum k function ko call kar lo.

Q ki if target is 22=> the find 11 first => you will get set 1. and automitacally you will get subset 2 od 11 remaining

[Khandagale-Saurabh]

Q]Count of Subset sum

Same he hai bs false ko 0 and true ko 1 karo and replace || ko + k saat

public static void main(String[] args) {
    int[] A = {1, 2, 1};
    int N = A.length;
    int sum = 3;

Ans===> 2

import java.util.*;
public class Main {
    // Function to find the no. of subsets having the given sum
    static int findSubsetSum(int A[], int N, int sum) {
        // First, we initialise the dp
        int[][] dp = new int[N + 1][sum + 1];

        // To initialise the first value of the dp
        dp[0][0] = 1;

        for (int k = 1; k <= sum; k++) {
            dp[0][k] = 0;
        }

        for (int k = 1; k <= N; k++) {
            for (int l = 0; l <= sum; l++) {
                // If element value is greater than the sum value
                if (A[k - 1] > l)
                    dp[k][l] = dp[k - 1][l];
                else {
                    dp[k][l] = dp[k - 1][l] + dp[k - 1][l - A[k - 1]];
                }
            }
        }
        return dp[N][sum];
    }

    // Main Program
    public static void main(String[] args) {
        int[] A = {1, 2, 1};
        int N = A.length;
        int sum = 3;

        // To print the output of counting the number of subsets
        System.out.println("Total number of subsets having sum " + sum + " = " +findSubsetSum(A, N, sum));
    }
}