Find number of solutions of a linear equation of n variables | A Dynamic programming based C ++ program to find number of non - negative solutions for a given linear equation ; Returns count of solutions for given rhs and coefficients coeff [ 0. . n - 1 ] ; Create and initialize a table to store results of subproblems ; Fill table in bottom up manner ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSol ( int coeff [ ] , int n , int rhs ) { int dp [ rhs + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = coeff [ i ] ; j <= rhs ; j ++ ) dp [ j ] += dp [ j - coeff [ i ] ] ; return dp [ rhs ] ; } int main ( ) { int coeff [ ] = { 2 , 2 , 5 } ; int rhs = 4 ; int n = sizeof ( coeff ) / sizeof ( coeff [ 0 ] ) ; cout << countSol ( coeff , n , rhs ) ; return 0 ; }