What is the brute force approach and complexity for Coin Change?

Recurse on the amount left for every coin that fits; no memory with time complexity O(C^A) and space complexity O(A).

What is the optimal approach and complexity for Coin Change?

dp[a] = fewest coins for each amount, filled from 0 up; one min per coin with optimal time complexity O(A · C) and space complexity O(A).

How do you identify the pattern for Coin Change?

Look for key signals in the prompt: "fewest coins" indicates The goal is a minimum count, not a maximum value. Each dp[a] takes a min over the last coin.; "unlimited supply of every coin" indicates Coins can repeat, so dp[a] reads dp[a − c] from the same table, which can already include coin c.; "return -1 if the amount cannot be made" indicates Some amounts are unreachable. Use a sentinel value (amount + 1) and check it at the end..

Coin Change

Medium·LeetCode #322 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given coins of several values and a total amount. You have an unlimited supply of every coin.

Find the fewest coins that add up to exactly amount. If no mix of the coins can make amount, return -1.

Input

coins, a list of coin values, and amount, the total you want to make.

Output

The fewest number of coins that add up to amount, or -1 if the amount cannot be made.

Example 1

Input: coins = [1, 2, 5], amount = 11

Output: 3

11 = 5 + 5 + 1. No other mix uses fewer than three coins.

Example 2

Input: coins = [2], amount = 3

Output: -1

Only 2s are available, and 3 is odd, so 3 cannot be made.

Example 3

Input: coins = [1], amount = 0

Output: 0

The amount is 0, so no coins are needed.

Constraints

• 1 ≤ coins.length ≤ 12
• 1 ≤ coins[i] ≤ 2^31 − 1
• 0 ≤ amount ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“fewest coins”

→ The goal is a minimum count, not a maximum value. Each dp[a] takes a min over the last coin.

“unlimited supply of every coin”

→ Coins can repeat, so dp[a] reads dp[a − c] from the same table, which can already include coin c.

“return -1 if the amount cannot be made”

→ Some amounts are unreachable. Use a sentinel value (amount + 1) and check it at the end.

Approach Complexity Ladder

Brute Force — try every coin, recurse on what is leftO(C^A)O(A)

Recurse on the amount left for every coin that fits; no memory

Optimal — bottom-up table over the amountO(A · C)O(A)

dp[a] = fewest coins for each amount, filled from 0 up; one min per coin

Brute Force Intuition

To make a, try every coin that fits in a. For each coin, find the fewest coins for a − coin with the same method, then add one coin. Keep the smallest result. An amount of 0 costs 0 coins.

Recognition rule for this sub-pattern:

Items can repeat — capacity loop goes low → high. Order of loops decides combinations vs permutations.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture