Check if it is possible to get given sum by taking one element from each row | C ++ implementation to find whether is it possible to make sum equal to K ; Function that prints whether is it possible to make sum equal to K ; Base case ; Condition if we can make sum equal to current column by using above rows ; Iterate through current column and check whether we can make sum less than or equal to k ; Printing whether is it possible or not ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void PossibleSum ( int n , int m , vector < vector < int > > v , int k ) { int dp [ n + 1 ] [ k + 1 ] = { 0 } ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j <= k ; j ++ ) { if ( dp [ i ] [ j ] == 1 ) { for ( int d = 0 ; d < m ; d ++ ) { if ( ( j + v [ i ] [ d ] ) <= k ) { dp [ i + 1 ] [ j + v [ i ] [ d ] ] = 1 ; } } } } } if ( dp [ n ] [ k ] == 1 ) cout << " YES STRNEWLINE " ; else cout << " NO STRNEWLINE " ; } int main ( ) { int N = 2 , M = 10 , K = 5 ; vector < vector < int > > arr = { { 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 } , { 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 } } ; PossibleSum ( N , M , arr , K ) ; return 0 ; }