Sum of length of two smallest subsets possible from a given array with sum at least K | C ++ program for the above approach ; Function to calculate sum of lengths of two smallest subsets with sum >= K ; Sort the array in ascending order ; Stores suffix sum of the array ; Update the suffix sum array ; Stores all dp - states ; Initialize all dp - states with a maximum possible value ; Base Case ; Traverse the array arr [ ] ; Iterate over the range [ 0 , K ] ; If A [ i ] is equal to at least the required sum j for the current state ; If the next possible state doesn 't exist ; Otherwise , update the current state to the minimum of the next state and state including the current element A [ i ] ; Traverse the suffix sum array ; If suffix [ i ] - dp [ i ] [ K ] >= K ; Sum of lengths of the two smallest subsets is obtained ; Return - 1 , if there doesn 't  exist any subset of sum >= K ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1e9 ; int MinimumLength ( int A [ ] , int N , int K ) { sort ( A , A + N ) ; int suffix [ N + 1 ] = { 0 } ; for ( int i = N - 1 ; i >= 0 ; i -- ) suffix [ i ] = suffix [ i + 1 ] + A [ i ] ; int dp [ N + 1 ] [ K + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) for ( int j = 0 ; j <= K ; j ++ ) dp [ i ] [ j ] = MAX ; dp [ N ] [ 0 ] = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = K ; j >= 0 ; j -- ) { if ( j <= A [ i ] ) { dp [ i ] [ j ] = A [ i ] ; continue ; } if ( dp [ i + 1 ] [ j - A [ i ] ] == MAX ) dp [ i ] [ j ] = MAX ; else dp [ i ] [ j ] = min ( dp [ i + 1 ] [ j ] , dp [ i + 1 ] [ j - A [ i ] ] + A [ i ] ) ; } } for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( suffix [ i ] - dp [ i ] [ K ] >= K ) { return N - i ; } } return -1 ; } int main ( ) { int arr [ ] = { 7 , 4 , 5 , 6 , 8 } ; int K = 13 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << MinimumLength ( arr , N , K ) ; return 0 ; }