-
Notifications
You must be signed in to change notification settings - Fork 1
/
CoinChange_1.ts
35 lines (29 loc) · 1.62 KB
/
CoinChange_1.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Problem: Given the infinite supply of the denominations, find out the total number of unique ways to make the total amount.
*
* Solution: Brute force solution finds out all the possible ways of making the coin change by creating
* all the subsets possible with the given denominations that makes up the total target amount.
*
* Complexity: Time O(2^(T+C)) C being the denominations and T being the max total.
* Complexity: Space O(T+C) as the max depth for recursion.
*
* @param denominations
* @param totalAmount
*/
function countCoinChangeBF(denominations: number[], totalAmount: number, item: number = 0): number {
// Base condition to exit, if there are no items left there is 0 ways.
if (item >= denominations.length) return 0;
// Base condition to return say there is 1 way to make target amount as 0.
if (totalAmount === 0) return 1;
// Include the denomination in the total count, only if it is less than total amount.
const totalAmountWithInclusion = (denominations[item] <= totalAmount) ?
countCoinChangeBF(denominations, totalAmount - denominations[item], item) :
0;
// Exclude the denomination without making any total amount change.
const totalAmountWithExclusion = countCoinChangeBF(denominations, totalAmount, item + 1);
return totalAmountWithExclusion + totalAmountWithInclusion;
}
function testCoinChangeBF(denominations: number[], totalAmount: number) {
console.log(`Total Ways of making coin change for denominations: ${denominations} and total amount: ${totalAmount} = ${countCoinChangeBF(denominations, totalAmount)}`)
}
testCoinChangeBF([1, 2, 3], 5);