Tejav
#322

Coin Change

Medium
ArrayDynamic ProgrammingBreadth-First Search
LeetCode ↗

Approaches

💡

Intuition

Time Space

The brute force approach tries every possible combination of coins to find the minimum number needed to reach the target amount. This method is straightforward but can be very inefficient as it explores all possibilities.

⚙️

Algorithm

3 steps
  1. 1Step 1: Generate all combinations of coins that sum up to the target amount.
  2. 2Step 2: Keep track of the number of coins used in each combination.
  3. 3Step 3: Return the minimum number of coins from all valid combinations, or -1 if no combination sums to the target.
solution.py10 lines
1# Full working Python code
2from itertools import combinations_with_replacement
3
4def coinChange(coins, amount):
5    min_coins = float('inf')
6    for r in range(1, amount + 1):
7        for combo in combinations_with_replacement(coins, r):
8            if sum(combo) == amount:
9                min_coins = min(min_coins, len(combo))
10    return min_coins if min_coins != float('inf') else -1

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.