Given an array Arr[] of size N and an integer K, the task is to find the length of the shortest subsequence having sum exactly K.
Examples:
Input: N = 5, K = 4, Arr[] = {1, 2, 2, 3, 4}
Output: 1
Explanation: Here, one can choose the last month and can get 4 working hours.Input: N = 3, K = 2, Arr[] = {1, 3, 5}
Output: -1
Explanation: Here, we can not get exactly 2 hours of work from any month.
Naive Approach: One of the most basic ways of solving the above problem is to generate all the subsets using Recursion and choose the subset with the smallest size which sums exactly K.
Time complexity: O (N * 2N).
Auxiliary Space: O(1)
Efficient Approach: The above problem can be solved in dynamic programming efficiently in the following way.
On each index there are two choices: either to include the element in the subsequence or not. To efficiently calculate this, use a two dimensional dp[][] array where dp[i][j] stores the minimum length of subsequence with sum j up to ith index.
Follow the below steps to implement the approach:
- Iterate from the start of the array.
- For each element there are two choices: either pick the element or not.
- If the value of the ith element is greater than the required sum (say X) to have subsequence sum K then it cannot be included.
- Otherwise do the following:
- Pick the ith element, update the required sum as (X-Arr[i]) and recursively do the same for the next index in step 5.
- Don’t insert the element in subsequence and call recursively for the next element.
- Store the minimum between these two in the dp[][] array.
- In each recursive call:
- If the required sum is 0 store the length of subsequence in dp[][] array.
- If it is already calculated for this same value of i and X it is already calculated then return the same.
- If not possible to achieve a subsequence sum exactly K from this state, return -1.
- The final value at dp[0][K] will denote the minimum subsequence length.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function which returns smallest// Subset size which sums exactly K// Or else returns -1// If there is no such subsetint minSize(vector<vector<int> >& dp, int i, vector<int>& arr, int k, int n){ // Size of empty subset is zero if (k == 0) return 0; // If the end of the array is reached // and k is not reduced to zero // then there is no subset // for current value of k if (i == n) return -1; // If some value of K is present // and it is required to make a choice // either to pick the ith element or // unpick it, and if it is already // computed, Return the answer directly if (dp[i][k] != 0) return dp[i][k]; int x, y, maxi; maxi = INT_MAX; // Initialize with maximum value since // it is required to find // the smallest subset x = y = maxi; // If the ith element is less than // or equal to k than // it can be a part of subset if (arr[i] <= k) { // Check whether there is a subset // for ( k - arr[i]) int m = minSize(dp, i + 1, arr, k - arr[i], n); // Check whether m is -1 or not if (m != -1) { // If m is not equal to -1 // that means there exists a subset // for the value ( k - arr[i] ) // update the subset size x = min(x, m + 1); } } // Exclude the current element and // check whether there is a subset for K // by trying the rest of the combinations int m = minSize(dp, i + 1, arr, k, n); // Check whether m is not equal to -1 if (m != -1) { // If m is not equal to -1 than // a subset is found for value // of K so update the // size of the subset y = min(y, m); } // If both x and y are equal // to maximum value, which means there // is no subset for the current value of K // either including the current element // or excluding the current element // In that case store -1 or else // store the minimum of ( x, y) // since we need the smallest subset return (dp[i][k] = (x == maxi and y == maxi) ? -1 : min(x, y));}// Function to calculate the// required length of subsequenceint seqLength(vector<int>& arr, int k){ int n = arr.size(); // Initialize the dp vector with 0 // in order to indicate that there // is no computed answer for any // of the sub problems vector<vector<int> > dp(n, vector<int>(k + 1, 0)); return minSize(dp, 0, arr, k, n);}// Driver Codeint main(){ int N = 5; int K = 4; vector<int> arr = { 1, 2, 2, 3, 4 }; // Function call cout << seqLength(arr, K) << endl; return 0;} |
Java
// Java Program of the above approach.import java.util.*;class GFG { // Function which returns smallest // Subset size which sums exactly K // Or else returns -1 // If there is no such subset static int minSize(int[][] dp, int i, int[] arr, int k, int n) { // Size of empty subset is zero if (k == 0) return 0; // If the end of the array is reached // and k is not reduced to zero // then there is no subset // for current value of k if (i == n) return -1; // If some value of K is present // and it is required to make a choice // either to pick the ith element or // unpick it, and if it is already // computed, Return the answer directly if (dp[i][k] != 0) return dp[i][k]; int x = 0, y = 0, maxi = Integer.MAX_VALUE; // Initialize with maximum value since // it is required to find // the smallest subset x = y = maxi; // If the ith element is less than // or equal to k than // it can be a part of subset if (arr[i] <= k) { // Check whether there is a subset // for ( k - arr[i]) int m1 = minSize(dp, i + 1, arr, k - arr[i], n); // Check whether m is -1 or not if (m1 != -1) { // If m is not equal to -1 // that means there exists a subset // for the value ( k - arr[i] ) // update the subset size x = Math.min(x, m1 + 1); } } // Exclude the current element and // check whether there is a subset for K // by trying the rest of the combinations int m2 = minSize(dp, i + 1, arr, k, n); // Check whether m is not equal to -1 if (m2 != -1) { // If m is not equal to -1 than // a subset is found for value // of K so update the // size of the subset y = Math.min(y, m2); } // If both x and y are equal // to maximum value, which means there // is no subset for the current value of K // either including the current element // or excluding the current element // In that case store -1 or else // store the minimum of ( x, y) // since we need the smallest subset return (dp[i][k] = (x == maxi && y == maxi) ? -1 : Math.min(x, y)); } // Function to calculate the // required length of subsequence static int seqLength(int[] arr, int k) { int n = arr.length; // Initialize the dp vector with 0 // in order to indicate that there // is no computed answer for any // of the sub problems int[][] dp = new int[n][k + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < k + 1; j++) { dp[i][j] = 0; } } return minSize(dp, 0, arr, k, n); } // Driver Code public static void main(String args[]) { int N = 5; int K = 4; int[] arr = { 1, 2, 2, 3, 4 }; // Function call System.out.print(seqLength(arr, K)); }}// This code is contributed by code_hunt. |
Python3
# python3 code for the above approach:INT_MAX = 2147483647# Function which returns smallest# Subset size which sums exactly K# Or else returns -1# If there is no such subsetdef minSize(dp, i, arr, k, n): # Size of empty subset is zero if (k == 0): return 0 # If the end of the array is reached # and k is not reduced to zero # then there is no subset # for current value of k if (i == n): return -1 # If some value of K is present # and it is required to make a choice # either to pick the ith element or # unpick it, and if it is already # computed, Return the answer directly if (dp[i][k] != 0): return dp[i][k] maxi = INT_MAX # Initialize with maximum value since # it is required to find # the smallest subset x = y = maxi # If the ith element is less than # or equal to k than # it can be a part of subset if (arr[i] <= k): # Check whether there is a subset # for ( k - arr[i]) m = minSize(dp, i + 1, arr, k - arr[i], n) # Check whether m is -1 or not if (m != -1): # If m is not equal to -1 # that means there exists a subset # for the value ( k - arr[i] ) # update the subset size x = min(x, m + 1) # Exclude the current element and # check whether there is a subset for K # by trying the rest of the combinations m = minSize(dp, i + 1, arr, k, n) # Check whether m is not equal to -1 if (m != -1): # If m is not equal to -1 than # a subset is found for value # of K so update the # size of the subset y = min(y, m) # If both x and y are equal # to maximum value, which means there # is no subset for the current value of K # either including the current element # or excluding the current element # In that case store -1 or else # store the minimum of ( x, y) # since we need the smallest subset dp[i][k] = -1 if (x == maxi and y == maxi) else min(x, y) return dp[i][k]# Function to calculate the# required length of subsequencedef seqLength(arr, k): n = len(arr) # Initialize the dp vector with 0 # in order to indicate that there # is no computed answer for any # of the sub problems dp = [[0 for _ in range(K+1)] for _ in range(n)] return minSize(dp, 0, arr, k, n)# Driver Codeif __name__ == "__main__": N = 5 K = 4 arr = [1, 2, 2, 3, 4] # Function call print(seqLength(arr, K)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approach:using System;class GFG { // Function which returns smallest // Subset size which sums exactly K // Or else returns -1 // If there is no such subset static int minSize(int[, ] dp, int i, int[] arr, int k, int n) { // Size of empty subset is zero if (k == 0) return 0; // If the end of the array is reached // and k is not reduced to zero // then there is no subset // for current value of k if (i == n) return -1; // If some value of K is present // and it is required to make a choice // either to pick the ith element or // unpick it, and if it is already // computed, Return the answer directly if (dp[i, k] != 0) return dp[i, k]; int x = 0, y = 0, maxi = Int32.MaxValue; // Initialize with maximum value since // it is required to find // the smallest subset x = y = maxi; // If the ith element is less than // or equal to k than // it can be a part of subset if (arr[i] <= k) { // Check whether there is a subset // for ( k - arr[i]) int m1 = minSize(dp, i + 1, arr, k - arr[i], n); // Check whether m is -1 or not if (m1 != -1) { // If m is not equal to -1 // that means there exists a subset // for the value ( k - arr[i] ) // update the subset size x = Math.Min(x, m1 + 1); } } // Exclude the current element and // check whether there is a subset for K // by trying the rest of the combinations int m2 = minSize(dp, i + 1, arr, k, n); // Check whether m is not equal to -1 if (m2 != -1) { // If m is not equal to -1 than // a subset is found for value // of K so update the // size of the subset y = Math.Min(y, m2); } // If both x and y are equal // to maximum value, which means there // is no subset for the current value of K // either including the current element // or excluding the current element // In that case store -1 or else // store the minimum of ( x, y) // since we need the smallest subset return (dp[i, k] = (x == maxi && y == maxi) ? -1 : Math.Min(x, y)); } // Function to calculate the // required length of subsequence static int seqLength(int[] arr, int k) { int n = arr.Length; // Initialize the dp vector with 0 // in order to indicate that there // is no computed answer for any // of the sub problems int[, ] dp = new int[n, k + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < k + 1; j++) { dp[i, j] = 0; } } return minSize(dp, 0, arr, k, n); } // Driver Code public static void Main() { int N = 5; int K = 4; int[] arr = { 1, 2, 2, 3, 4 }; // Function call Console.WriteLine(seqLength(arr, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function which returns smallest // Subset size which sums exactly K // Or else returns -1 // If there is no such subset function minSize(dp, i, arr, k, n) { // Size of empty subset is zero if (k == 0) return 0; // If the end of the array is reached // and k is not reduced to zero // then there is no subset // for current value of k if (i == n) return -1; // If some value of K is present // and it is required to make a choice // either to pick the ith element or // unpick it, and if it is already // computed, Return the answer directly if (dp[i][k] != 0) return dp[i][k]; let x, y, maxi; maxi = Number.MAX_VALUE; // Initialize with maximum value since // it is required to find // the smallest subset x = y = maxi; // If the ith element is less than // or equal to k than // it can be a part of subset if (arr[i] <= k) { // Check whether there is a subset // for ( k - arr[i]) let m = minSize(dp, i + 1, arr, k - arr[i], n); // Check whether m is -1 or not if (m != -1) { // If m is not equal to -1 // that means there exists a subset // for the value ( k - arr[i] ) // update the subset size x = Math.min(x, m + 1); } } // Exclude the current element and // check whether there is a subset for K // by trying the rest of the combinations let m = minSize(dp, i + 1, arr, k, n); // Check whether m is not equal to -1 if (m != -1) { // If m is not equal to -1 than // a subset is found for value // of K so update the // size of the subset y = Math.min(y, m); } // If both x and y are equal // to maximum value, which means there // is no subset for the current value of K // either including the current element // or excluding the current element // In that case store -1 or else // store the minimum of ( x, y) // since we need the smallest subset return (dp[i][k] = (x == maxi && y == maxi) ? -1 : Math.min(x, y)); } // Function to calculate the // required length of subsequence function seqLength(arr, k) { let n = arr.length; // Initialize the dp vector with 0 // in order to indicate that there // is no computed answer for any // of the sub problems let dp = new Array(n) for (let i = 0; i < dp.length; i++) { dp[i] = new Array(k + 1).fill(0) } return minSize(dp, 0, arr, k, n); } // Driver Code let N = 5; let K = 4; let arr = [1, 2, 2, 3, 4]; // Function call document.write(seqLength(arr, K) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output
1
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Initialize a 2D vector dp of size (n+1) x (k+1) where n is the size of the input vector arr.
- Initialize the base case dp[i][0] = 0 for all i from 0 to n.
- For each element arr[i] in the input vector arr, and for each sum value j from 1 to k:
a. If arr[i] is greater than j, set dp[i][j] = dp[i-1][j].
b. Otherwise, set dp[i][j] = min(dp[i-1][j-arr[i]] + 1, dp[i-1][j]). - Return dp[n][k] if it is less than INT_MAX, otherwise return -1.
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the required length of subsequenceint seqLength(vector<int>& arr, int k){ int n = arr.size(); // Initialize the DP table vector<vector<int> > dp(n + 1, vector<int>(k + 1, 1e9)); // Base case: If the sum is 0, we need 0 elements for (int i = 0; i <= n; i++) dp[i][0] = 0; // Fill the DP table iteratively for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { // If the current element is greater than the current sum if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } // If the current element is less than or equal to the current sum else { // Take the minimum of the two cases: // 1. Include the current element // 2. Exclude the current element dp[i][j] = min(dp[i - 1][j - arr[i - 1]] + 1, dp[i - 1][j]); } } } // Check if the result is greater than or equal to 1e9 return (dp[n][k] >= 1e9) ? -1 : dp[n][k];}// Driver Codeint main(){ int N = 5; int K = 4; vector<int> arr = { 1, 2, 2, 3, 4 }; // Function call cout << seqLength(arr, K) << endl; return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;class Main { // Function to calculate the required length of subsequence static int seqLength(ArrayList<Integer> arr, int k) { int n = arr.size(); // Initialize the DP table int[][] dp = new int[n + 1][k + 1]; for (int[] row : dp) Arrays.fill(row, 1000000000); // Base case: If the sum is 0, we need 0 elements for (int i = 0; i <= n; i++) dp[i][0] = 0; // Fill the DP table iteratively for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { // If the current element is greater than the current sum if (arr.get(i - 1) > j) { dp[i][j] = dp[i - 1][j]; } // If the current element is less than or equal to the current sum else { // Take the minimum of the two cases: // 1. Include the current element // 2. Exclude the current element dp[i][j] = Math.min(dp[i - 1][j - arr.get(i - 1)] + 1, dp[i - 1][j]); } } } // Check if the result is greater than or equal to 1e9 return (dp[n][k] >= 1000000000) ? -1 : dp[n][k]; } // Driver Code public static void main(String[] args) { int N = 5; int K = 4; ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 4)); // Function call System.out.println(seqLength(arr, K)); }} |
Python3
# Python program for the above approach# Function to calculate the required length of subsequencedef seqLength(arr, k): n = len(arr) # Initialize the DP table dp = [[1e9 for j in range(k + 1)] for i in range(n + 1)] # Base case: If the sum is 0, we need 0 elements for i in range(n + 1): dp[i][0] = 0 # Fill the DP table iteratively for i in range(1, n + 1): for j in range(1, k + 1): # If the current element is greater than the current sum if arr[i - 1] > j: dp[i][j] = dp[i - 1][j] # If the current element is less than or equal to the current sum else: # Take the minimum of the two cases: # 1. Include the current element # 2. Exclude the current element dp[i][j] = min(dp[i - 1][j - arr[i - 1]] + 1, dp[i - 1][j]) # Check if the result is greater than or equal to 1e9 return -1 if dp[n][k] >= 1e9 else dp[n][k]# Driver Codeif __name__ == '__main__': N = 5 K = 4 arr = [1, 2, 2, 3, 4] # Function call print(seqLength(arr, K)) |
C#
using System;using System.Collections.Generic;public class GFG { // Function to calculate the required length of subsequence static int seqLength(List<int> arr, int k) { int n = arr.Count; // Initialize the DP table List<List<int>> dp = new List<List<int>>(); for (int i = 0; i <= n; i++) { dp.Add(new List<int>()); for (int j = 0; j <= k; j++) { dp[i].Add(1000000000); } } // Base case: If the sum is 0, we need 0 elements for (int i = 0; i <= n; i++) { dp[i][0] = 0; } // Fill the DP table iteratively for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { // If the current element is greater than the current sum if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } // If the current element is less than or equal to the current sum else { // Take the minimum of the two cases: // 1. Include the current element // 2. Exclude the current element dp[i][j] = Math.Min(dp[i - 1][j - arr[i - 1]] + 1, dp[i - 1][j]); } } } // Check if the result is greater than or equal to 1e9 return (dp[n][k] >= 1000000000) ? -1 : dp[n][k]; } // Driver Code public static void Main() { int K = 4; List<int> arr = new List<int>() { 1, 2, 2, 3, 4 }; // Function call Console.WriteLine(seqLength(arr, K)); }} |
Javascript
// Function to calculate the required length of subsequencefunction seqLength(arr, k) { let n = arr.length; // Initialize the DP table let dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(1e9)); // Base case: If the sum is 0, we need 0 elements for (let i = 0; i <= n; i++) { dp[i][0] = 0; } // Fill the DP table iteratively for (let i = 1; i <= n; i++) { for (let j = 1; j <= k; j++) { // If the current element is greater than the current sum if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } // If the current element is less than or equal to the current sum else { // Take the minimum of the two cases: // 1. Include the current element // 2. Exclude the current element dp[i][j] = Math.min(dp[i - 1][j - arr[i - 1]] + 1, dp[i - 1][j]); } } } // Check if the result is greater than or equal to 1e9 return dp[n][k] >= 1e9 ? -1 : dp[n][k];}let N = 5;let K = 4;let arr = [1, 2, 2, 3, 4];// Function callconsole.log(seqLength(arr, K)); |
Output:
1
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
