Skip to content

Instantly share code, notes, and snippets.

@renato04
Last active November 6, 2020 13:29
Show Gist options
  • Save renato04/2f3c97a08de3af8558fc43a5f39eb3ba to your computer and use it in GitHub Desktop.
Save renato04/2f3c97a08de3af8558fc43a5f39eb3ba to your computer and use it in GitHub Desktop.
Class to resolve coin change problem using recursion
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