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 + 3z = 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++

Download   Run Code

Output:

Total number of solutions are 4

Java

Download   Run Code

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++

Download   Run Code

Output:

Total number of solutions are 4

Java

Download   Run Code

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.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Sort by:   newest | oldest | most voted
Tim Stoev
Tim Stoev

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

wpDiscuz