Minimum count of numbers required from given array to represent S | C ++ implementation to find the minimum number of sequence required from array such that their sum is equal to given S ; Function to find the count of minimum length of the sequence ; Loop to initialize the array as infinite in the row 0 ; Loop to find the solution by pre - computation for the sequence ; Minimum possible for the previous minimum value of the sequence ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Count ( int S [ ] , int m , int n ) { vector < vector < int > > table ( m + 1 , vector < int > ( n + 1 , 0 ) ) ; for ( int i = 1 ; i <= n ; i ++ ) { table [ 0 ] [ i ] = INT_MAX - 1 ; } for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( S [ i - 1 ] > j ) { table [ i ] [ j ] = table [ i - 1 ] [ j ] ; } else { table [ i ] [ j ] = min ( table [ i - 1 ] [ j ] , table [ i ] [ j - S [ i - 1 ] ] + 1 ) ; } } } return table [ m ] [ n ] ; } int main ( ) { int arr [ ] = { 9 , 6 , 5 , 1 } ; int m = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << Count ( arr , m , 11 ) ; return 0 ; }