How to Solve Coin Change Problem?

Let's dive in!

Given an array of coins and a total sum, find the fewest number of coins needed to make the sum. Return -1 if impossible.

Problem Statement

Example-  Input: [1,2,5,9,8] Sum: 17 Output: 2 Explanation: Two coins require to make the desired sum [9,8]

Use recursion to check all possible combinations of coins to find the minimum number of coins needed to create the given sum. Update the number of coins needed with each iteration.

Simple Approach

Time complexity: Exponential. (every recursive call is making n recursive calls) Space complexity: O(1)

Solve the problem by breaking it down into smaller subproblems and using a bottom-up approach to compute  dp[i] (1<=i<=subproblems) which stores the minimum number of coins needed to create the sum.

Efficient Approach: Dynamic Programming

Time complexity: O(n*sum)  n- no of distinct coins, sum- desired sum. Space complexity: O(sum)

Want to explore these approaches and learn how to implement them in various programming languages?

Click on the link below to start your journey.