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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> using namespace std; // Function to count total number of possible solutions of a // linear equation of k variables int count(int coeff[], int k, int rhs) { // if rhs becomes 0, return 1 (solution found) if (rhs == 0) return 1; // return 0 (solution do not exist) if rhs becomes negative or // no coefficient is left if (rhs < 0 || k < 0) return 0; // Case 1. include current coefficient coeff[k] in solution and // recurse with remaining value (rhs - coeff[k]) int include = count(coeff, k, rhs - coeff[k]); // Case 2. exclude current coefficient coeff[k] from solution and // recurse for remaining coefficients (k - 1) int exclude = count(coeff, k - 1, rhs); // return total ways by including or excluding current coefficient return include + exclude; } // main function int main() { // k coefficients of given equation int coeff[] = { 1, 2, 3 }; int k = sizeof(coeff) / sizeof(coeff[0]); int rhs = 4; cout << "Total number of solutions are " << count(coeff, k - 1, rhs); return 0; } |

`Output:`

Total number of solutions are 4

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class TotalCount { // Function to count total number of possible solutions of a // linear equation of k variables public static int count(int coeff[], int k, int rhs) { // if rhs becomes 0, solution is found if (rhs == 0) return 1; // return 0 if rhs becomes negative or no coefficient is left if (rhs < 0 || k < 0) return 0; // Case 1. include current coefficient coeff[k] in solution and // recurse with remaining value (rhs - coeff[k]) int include = count(coeff, k, rhs - coeff[k]); // Case 2. exclude current coefficient coeff[k] from solution and // recurse for remaining coefficients (k - 1) int exclude = count(coeff, k - 1, rhs); // return total ways by including or excluding current coefficient return include + exclude; } public static void main (String[] args) { // k coefficients of given equation int[] coeff = { 1, 2, 3 }; final int k = coeff.length; int rhs = 4; System.out.println("Total number of solutions are " + count(coeff, k - 1, rhs)); } } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <unordered_map> using namespace std; // Function to count total number of possible solutions of a // linear equation of k variables int count(int coeff[], int k, int rhs, auto &lookup) { // if rhs becomes 0, return 1 (solution found) if (rhs == 0) return 1; // return 0 (solution do not exist) if rhs becomes negative or // no coefficient is left if (rhs < 0 || k < 0) return 0; // construct a unique map key from dynamic elements of the input string key = to_string(k) + "|" + to_string(rhs); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { int include = count(coeff, k, rhs - coeff[k], lookup); // case 1 int exclude = count(coeff, k - 1, rhs, lookup); // case 2 // assign total ways by including or excluding current coefficient lookup[key] = include + exclude; } // return solution to current sub-problem return lookup[key]; } // main function int main() { // k coefficients of given equation int coeff[] = { 1, 2, 3 }; int k = sizeof(coeff) / sizeof(coeff[0]); int rhs = 4; // create a map to store solutions of subproblems unordered_map<string, int> lookup; cout << "Total number of solutions are " << count(coeff, k - 1, rhs, lookup); return 0; } |

`Output:`

Total number of solutions are 4

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.Map; import java.util.HashMap; class TotalCount { // Function to count total number of possible solutions of a // linear equation of k variables public static int count(int coeff[], int k, int rhs, Map<String, Integer> lookup) { // if rhs becomes 0, solution is found if (rhs == 0) return 1; // return 0 if rhs becomes negative or no coefficient is left if (rhs < 0 || k < 0) return 0; // construct a unique map key from dynamic elements of the input String key = String.valueOf(k) + "|" + String.valueOf(rhs); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.get(key) == null) { int include = count(coeff, k, rhs - coeff[k], lookup); // Case 1 int exclude = count(coeff, k - 1, rhs, lookup); // Case 2 // return total ways by including or excluding current coeff lookup.put(key, include + exclude); } // return solution to current sub-problem return lookup.get(key); } public static void main (String[] args) { // k coefficients of given equation int[] coeff = { 1, 2, 3 }; final int k = coeff.length; final int rhs = 4; // create a map to store solutions of subproblems Map<String, Integer> lookup = new HashMap<String, Integer>(); System.out.println("Total number of solutions are " + count(coeff, k - 1, rhs, lookup)); } } |

`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 🙂

## Leave a Reply

x + 2y + 3y = 4.must be x + 2y + 3z = 4

It is a stupid typo but still nice to be fixed

Thanks for bringing this to our notice. We have corrected it. Happy coding 🙂