Q14 Subset Sum Equal To K - Coding Ninjas
Sat Jul 22 2023 07:36:26 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.* ;
import java.io.*;
public class Solution {
public static boolean subsetSumToK(int n, int k, int arr[]){
// return solve(arr , n-1 , k , new Boolean[n][k+1]);
//Tabulization -> n*k | Sc- n*k
boolean[][] dp = new boolean[n][k+1];
for(int i = 0 ;i < n ; i++){
for(int j = 0 ; j < k+1 ; j++){
if(i == 0){
if(j == 0 || j-arr[0] == 0)
dp[i][j] = true;
else dp[i][j] = false;
}
else{
boolean take = false , notake = false;
if(j-arr[i] >= 0)
take = dp[i-1][j-arr[i]];
notake = dp[i-1][j];
dp[i][j] = take||notake;
}
}
}
return dp[n-1][k];
}
//Recursion -> 2^(n*k) Memoization-> 2*n*k | SC- n*k + n*k
public static boolean solve(int arr[] ,int idx , int k , Boolean[][] dp){
if(k < 0)
return false;
if(idx == 0){
if(k == 0 || k - arr[0]== 0)
return true;
return false;
}
if(dp[idx][k] != null)
return dp[idx][k];
//take / notake faith calls from (n-1,k)
boolean take = solve(arr ,idx-1 , k-arr[idx] , dp );
boolean notake = solve(arr , idx-1 , k , dp);
return dp[idx][k] = take||notake;
}
}
content_copyCOPY
https://www.codingninjas.com/studio/problems/subset-sum-equal-to-k_1550954?leftPanelTab
Comments