Subset Sum Equal To K

companies in which it was asked

problem statement

space optimization

import java.util.* ;
import java.io.*; 
public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
       boolean prev[] = new boolean[k + 1];
        
        // Initialize the first row of the DP table
        prev[0] = true;

        // Initialize the first column of the DP table
        if (arr[0] <= k) {
            prev[arr[0]] = true;
        }

        // Fill in the DP table using bottom-up approach
        for (int ind = 1; ind < n; ind++) {
            // Create an array to store the current row of the DP table
            boolean cur[] = new boolean[k + 1];
            
            // Initialize the first column of the current row
            cur[0] = true;
            
            for (int target = 1; target <= k; target++) {
                // Calculate if the current target can be achieved without taking the current element
                boolean notTaken = prev[target];
                
                // Calculate if the current target can be achieved by taking the current element
                boolean taken = false;
                if (arr[ind] <= target) {
                    taken = prev[target - arr[ind]];
                }
                
                // Store the result in the current row of the DP table
                cur[target] = notTaken || taken;
            }
            
            // Update the previous row with the current row
            prev = cur;
        }

        // The final result is stored in the last cell of the previous row
        return prev[k];
    }

       
}

Tabulation

import java.util.* ;
import java.io.*; 
public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
        boolean[][] dp = new boolean[n][k + 1];

        // Initialization
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
      if (arr[0] <= k) {
            dp[0][arr[0]] = true;
        }

        // Bottom-up DP
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                boolean notTake = dp[i - 1][j];
                boolean take = false;
                if (arr[i] <= j) {
                    take = dp[i - 1][j - arr[i]];
                }
                dp[i][j] = (notTake || take);
            }
        }

        return dp[n - 1][k];
     }
       
}

Memoization

import java.util.* ;
import java.io.*; 
public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
        boolean[][] dp=new boolean[n][k+1];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],false);
        }
        return f(n-1,k,arr,dp);
    }
  static  boolean f(int ind, int tar, int a[],boolean[][]dp){
      if(tar==0) return true;
      if(ind==0) return (a[0]==tar);
       if (dp[ind][tar] == true) return true; 
      boolean notTake=f(ind-1,tar,a,dp);
      boolean take=false;
      if(a[ind]<=tar){
          take=f(ind-1,tar-a[ind],a,dp);
      }
      return dp[ind][tar]=(notTake||take);
  }
}

Recursive

import java.util.* ;
import java.io.*; 
public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
        return f(n-1,k,arr);
    }
  static  boolean f(int ind, int tar, int a[]){
      if(tar==0) return true;
      if(ind==0) return (a[0]==tar);

      boolean notTake=f(ind-1,tar,a);
      boolean take=false;
      if(a[ind]<=tar){
          take=f(ind-1,tar-a[ind],a);
      }
      return (notTake||take);
  }
}

Recursive Approach:

Time Complexity: Exponential, O(2^n), where n is the size of the input array. This is because the function makes two recursive calls for each element in the array.

Space Complexity: O(n), where n is the depth of the recursive call stack.

Memoization (Top-down Dynamic Programming) Approach:

Time Complexity: O(n * k), where n is the size of the input array and k is the target sum. This is because there are n * k subproblems, and each subproblem takes constant time to solve once computed.

Space Complexity: O(n * k), as the memoization table has n * k entries.

Tabulation (Bottom-up Dynamic Programming) Approach:

Time Complexity: O(n * k), where n is the size of the input array and k is the target sum. This is because there is a nested loop over n and k.

Space Complexity: O(n * k), as the tabulation table has n * k entries.

Optimized Tabulation with Rolling Array (prev and cur):

Time Complexity: O(n * k), where n is the size of the input array and k is the target sum. Similar to the regular tabulation approach.

Space Complexity: O(k), as only two rows (prev and cur) are stored at any given time.

In terms of time complexity, all three dynamic programming approaches (Memoization, Tabulation, and Optimized Tabulation) have the same time complexity. However, the optimized tabulation version has a lower space complexity compared to the other two, making it more memory-efficient.