Last active
November 6, 2020 13:29
-
-
Save renato04/2f3c97a08de3af8558fc43a5f39eb3ba to your computer and use it in GitHub Desktop.
Class to resolve coin change problem using recursion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class CoinChangeProblemSolver | |
{ | |
public int Solve(int[] coins, int ammount) | |
{ | |
int count(int[] c, int m, int n) | |
{ | |
// If n is 0 then there is -1 solution | |
// (do not include any coin) | |
if (n == 0) | |
return 1; | |
// If n is less than 0 then no | |
// solution exists | |
if (n < 0) | |
return 0; | |
// If there are no coins and n | |
// is greater than 0, then no | |
// solution exist | |
if (m <= 0 && n >= 1) | |
return 0; | |
// count is sum of solutions (i) | |
// including S[m-1] (ii) excluding S[m-1] | |
return count(c, m - 1, n) + | |
count(c, m, n - c[m - 1]); | |
} | |
return count(coins, coins.Length, ammount); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment