# Total possible solutions to linear equation of k variables

Given a linear equation of k variables, count total number of possible solutions of it.

For example,

Input: coeff = {1, 3, 5, 7}, rhs = 8

Output:Total number of solutions are 6

Above input represents the equation a + 3b + 5c + 7d = 8.

( a = 1, b = 0, c = 0, d = 1 )
( a = 0, b = 1, c = 1, d = 0 )
( a = 2, b = 2, c = 0, d = 0 )
( a = 3, b = 0, c = 1, d = 0 )
( a = 5, b = 1, c = 0, d = 0 )
( a = 8, b = 0, c = 0, d = 0 )

Input: coeff = {1, 2, 3}, rhs = 4

Output:Total number of solutions are 4

Above input represents the equation x + 2y + 3y = 4.

( x = 1, y = 0, z = 1 )
( x = 0, y = 2, z = 0 )
( x = 2, y = 1, z = 0 )
( x = 4, y = 0, z = 0 )

The problem is similar to finding total number of ways to get the denomination of coins. Here, coefficients of an equation can be considered as coins denominations and RHS of an equation can be considered as desired change. Let us begin by recursively defining the problem –

count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);

That is, for each coefficient of a variable

• We include current coefficient coeff[k] in solution and recurse with remaining value (rhs-coeff[k]).

• We exclude current coefficient coeff[k] from solution and recurse for remaining coefficients (k-1).

Finally, we return total ways by including or excluding current coefficient. The base case of the recursion is when solution is found (i.e. rhs becomes 0) or the solution doesn’t exist (when no coefficients are left or rhs becomes negative).

## C++

Output:

Total number of solutions are 4

## Java

Output:

Total number of solutions are 4

The time complexity of above solution is still exponential and auxiliary space used by the program is O(1).

The above solution has an optimal substructure as it can be broken down into smaller subproblems. It also clearly displays overlapping subproblems and we might end up solving the same sub-problem again and again. The repeated sub-problems can be seen by drawing recursion tree for higher values of desired change.

The problems having optimal substructure and overlapping subproblems can be solved using dynamic programming in which subproblem solutions are Memoized rather than computed again and again. The approach is illustrated below –

## C++

Output:

Total number of solutions are 4

## Java

Output:

Total number of solutions are 4

The time complexity of above solution is O(k x rhs) and auxiliary space used by the program is O(k x rhs).

Exercise: Write bottom-up version of above memoized solution.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Tim Stoev

x + 2y + 3y = 4.must be x + 2y + 3z = 4
It is a stupid typo but still nice to be fixed Guest

I think this solution is wrong, because it doesn’t add up the number of solutions for each different possible value that including coefficient takes. For example:

each variable takes a value in range [0 .. N] or [ 0 .. N/ Coeff (i) ]

taking “0” means to exclude that variable, so we’ll have something as following:

int count(int* Coeff, int n, rhs) {

if( rhs == 0) return 1;
for( int val = 0; val < N/Coeff[n-1]; val++)
count += count(coeff, k-1, rhs – coeff[n-1]* val );

} Guest

Wherever I mentioned N, I meant “rhs”, or the total sum.
There is “k-1” which I meant “n-1”; so here is the modified answer:

int count(int* Coeff, int n, int rhs) {

if( rhs == 0) return 1; // the solution is already found
if( rhs 0) return 0; // no solution was found for this combination

for( int possible_val = 0; possible_val < N/Coeff[n-1]; possible_val++)
count+= count(Coeff, n-1, rhs-Coeff[n-1]* possible_val);

}

thanks again