Sum of length of two smallest subsets possible from a given array with sum at least K | Python3 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
MAX = 1e9 NEW_LINE def MinimumLength ( A , N , K ) : NEW_LINE INDENT A . sort ( ) NEW_LINE suffix = [ 0 ] * ( N + 1 ) NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT suffix [ i ] = suffix [ i + 1 ] + A [ i ] NEW_LINE DEDENT dp = [ [ 0 ] * ( K + 1 ) ] * ( N + 1 ) NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for j in range ( K + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = MAX NEW_LINE DEDENT DEDENT dp [ N ] [ 0 ] = 0 NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( K , - 1 , - 1 ) : NEW_LINE INDENT if ( j <= A [ i ] ) : NEW_LINE INDENT dp [ i ] [ j ] = A [ i ] NEW_LINE continue NEW_LINE DEDENT if ( dp [ i + 1 ] [ j - A [ i ] ] == MAX ) : NEW_LINE INDENT dp [ i ] [ j ] = MAX NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i + 1 ] [ j ] , dp [ i + 1 ] [ j - A [ i ] ] + A [ i ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( suffix [ i ] - dp [ i ] [ K ] >= K ) : NEW_LINE INDENT return N - i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT arr = [ 7 , 4 , 5 , 6 , 8 ] NEW_LINE K = 13 NEW_LINE N = len ( arr ) NEW_LINE print ( MinimumLength ( arr , N , K ) ) NEW_LINE