Dsa
Backtracking
Medium
Combination of Coins
You have an unlimited supply of different coins and a target amount to make. Write a program to find all distinct combinations of coins that sum up to the target amount. Each combination should be presented as a list of the coins used. The order of coins in the list does not matter.
Input:
The first line contains an integer n (1 <= n <= 10) representing the number of coins.
The second line contains n integers representing the coin values (1 <= coin <= 50).
The third line contains an integer amount (1 <= amount <= 100).
Output:
Print each distinct combination in a new line, in sorted order based on combinations.
Example:
Input:
3
2 3 6
7
Output:
[2, 2, 3]
[3, 2, 2]
[6, 2]
[7]
Key concepts
backtrackingcombinatoricsdynamic programming
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now